0%

LeetCode题解35

发表于 更新于 分类于
本文字数： 1.5k 阅读时长 ≈ 1 分钟

LeetCode题解

第35题，搜索插入位置

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

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

示例 1:

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

示例 2:

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

示例 3:

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

示例 4:

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

原题如上，代码如下：

python版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        start = 0
        end = len(nums) - 1
        while start + 1 < end :
            mid = int((start + end)/2)
            if nums[mid] <= target : 
                start = mid
            else:
                end = mid
        if nums[start] >= target :
            return start
        if nums[end] >= target :
            return end
        return end+1

1V3BHs.png

c语言版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int searchInsert(int* nums, int numsSize, int target){
    int start = 0;
    int end = numsSize - 1;
    while(start + 1 < end){
        int mid = (start + end)/2;
        if(nums[mid] <= target){
            start = mid;
        }else{
            end = mid;
        }
    }
    if(nums[start] >= target){
        return start;
    }
    if(nums[end] >= target){
        return end;
    }
    return end+1;
}

1V8aPx.png

解析：

使用二分法查找：

1
2
3
4
5
6
7
8
while(start + 1 < end){
    int mid = (start + end)/2;
    if(nums[mid] <= target){
        start = mid;
    }else{
       	end = mid;
    }
}

使用mid将范围区间不断缩小，最后使其定位到[start，end]之间，其中end = start + 1。

循环条件为start + 1 < end ，等价于 start + 1 != end。

已知有序数组nums和target。则存在多种情况：

  1. target < nums[0]

    则此时start = 0 ，end = 1

    1
    2
    3
    if(nums[start] >= target){
        return start;
    }

    则返回 0。

  2. target = nums[i]

    则此时start = i，end = i + 1

    1
    2
    3
    if(nums[start] >= target){
        return start;
    }

    则返回 i。

  3. target > nums[i] target < nums[i+1]

    则此时start = i，end = i + 1

    1
    2
    3
    if(nums[end] >= target){
        return end;
    }

    则返回 i + 1。

  4. target > nums[numsSize - 1]

    则此时start = numsSize - 2，end = numsSize - 1

    1
    return end+1;

    则返回numsSize。