35. 搜索插入位置

Posted on In Views: Disqus:
LeetCode刷题系列。

描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:

1
2
输入: [1,3,5,6], 5
输出: 2

示例 2:

1
2
输入: [1,3,5,6], 2
输出: 1

示例 3:

1
2
输入: [1,3,5,6], 7
输出: 4

示例 4:

1
2
输入: [1,3,5,6], 0
输出: 0

来源：力扣（LeetCode）
链接：35. Search Insert Position

解题思路

本题略简单，应该主要是想考察二分法。不过为了比较还是给出两种解法。

第一种解法简单粗暴，算法复杂度为O(n)O(n)，设置一个指示变量index，遍历一遍数组，如果target比起nums[i]大，则index++，否则直接返回index，逻辑非常简单，可以直接在循环体内完成，如果作为一个函数，还需要一个默认的return语句，因此在循环体外面的结束还需要加一条return语句，否则提交无法通过。

具体代码见解法一。

第二种解法就是大名鼎鼎而又经典的二分法。

二分法原理虽然简单，但是比较容易出错，比如怎么求中位数，循环条件的设置，分支逻辑的规律等。

各自的注意点如下：

  • 取中位数的时候要避免在计算上出现整型溢出
    • int mid = (left + right) / 2; 的问题：在 left 和 right 很大的时候，left + right 会发生整型溢出，变成负数，通常建议采用int mid = left + (right - left) / 2或者无符号右移>>>（在C语言当中需要将普通右移>>与无符号转换unsigned int配合使用）
  • 循环条件设置
    • 把循环可以进行的条件写成 while(left < right)，在退出循环的时候，一定有 left == right 成立，此时返回 left 或者 right 都可以
  • 分支逻辑判断
    • 首先对于如果第 1 个分支的逻辑是“左边界排除中位数”（left = mid + 1），那么第 2 个分支的逻辑就一定是“右边界不排除中位数”（right = mid），反过来也成立
    • 如果第 2 个分支的逻辑是“右边界排除中位数”（right = mid - 1），那么第 2 个分支的逻辑就一定是“左边界不排除中位数”（left = mid），反之也成立

明天了这些注意点，代码写起来一般不容易出错，具体代码见解法二。

代码

解法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int searchInsert(int* nums, int numsSize, int target)
{
    int index  = 0;
    
    for(int i = 0; i <  numsSize; i++)
    {
        if(target > nums[i])
        {
            index++;
        }
        
        else
        {
            return index;
        }
    }
    
    return;
    
}

解法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int searchInsert(int* nums, int numsSize, int target)
{
    int left  = 0, right =  numsSize - 1;
    
    //如果target比nums数组当中最大的元素都大，则将target插到数组的最后，然后返回numsSize
    if(nums[numsSize - 1] < target) 
    {
        return numsSize;
    }
    
    while(left < right)
    {
        int mid = (left + right) >> 1;
        if(nums[mid] == target)
        {
            return mid;
        }
        else if(nums[mid] > target)
        {
            right = mid;
        }
        else
        {
            left = mid + 1;
        }
    }
    
    return right;
    
}

参考