Jasin Yip

计蒜客【挑战难题】系列讲解(十)寻找插入位置

题目

第10题:寻找插入位置

  给定一个已经升序排好序的数组,以及一个数target,如果target在数组中,返回它在数组中的位置。

  否则,返回target插入数组后它应该在的位置。
  假设数组中没有重复的数。以下是简单的示例:
  [1,3,5,6], 5 → 2
  [1,3,5,6], 2 → 1
  [1,3,5,6], 7 → 4
  [1,3,5,6], 0 → 0
  提示:输入一个整数n,以及其对应的数组A[n],最后输入target
  searchInsert(int A[], int n, int target)

样例输入

3
1 3 5
2

样例输出

1

C 实现

#include<stdio.h>
#define MAX 10000
int searchInsert(int A[], int n, int target);
int main(){
    int n, arr[MAX], target;
    scanf("%d",&n);
    for(int i = 0; i < n; i++){
        scanf("%d",&arr[i]);
    }
    scanf("%d",&target);
    printf("%d\n",searchInsert(arr, n, target));
    return 0;
}
int searchInsert(int A[], int n, int target){
    int i = 0;
    for(; i < n; i++){
        if(A[i] >= target)
            return i;
    }
    return i;
}

它如何工作

根据题意,我们得知是寻找目标数target在数组中的位置,而这个位置上的数如果等于target则此为需要的答案,否则,则表明该位置前一个元素小于target,后一个元素大于target,于是根据分析,得出我们需要在符合A[i] >= target时返回此时的i即为target的正确插入位置。

如有不懂,欢迎加入计蒜客QQ群咨询:

一群:239266679(满)
二群:228348940(满)
三群:159642279
四群:385386446

标签:c语言, 计蒜客, 挑战难题

已有 6 条评论

  1. acm弱菜 acm弱菜

    这给已经开了10000的数组 没有赋值的后面也没有显示吗?

  2. 打酱油一定得选最好的酱油瓶子

  3. I acquired often the Bailey Press button to get Xmas (excellent initial pair of shoes possibly) there is nothing absolutely love him or her! Most people continue to keep a few ankles and shins trendy and comfy as they are extra wonderful. They've been next excellent brand-new beloved wow gold (:

  4. 当你看到这条回复时这条回复就是:我和我的小伙伴们惊呆了

  5. Very pretty!! Thanks!!

  6. 我就喜欢挑人少的帖子回,我来文章必要火

添加新评论