LeetCode35:搜索位置插入


LeetCode地址

解题思路

给定一个非递减排序的数组nums，和一个目标值target。要求在数组中搜索目标值的位置，如果目标值存在，则返回其索引，如果目标值不存在，返回应该插入的位置索引。

暴力解法(左闭右开)

暴力解法的思路比较简单，遍历数组中的每个元素，如果当前元素大于等于目标值，说明目标值应该插入到当前位置或之前的位置，即返回当前索引。如果遍历完整个数组都没有找到大于等于目标值的元素，说明目标值应该插入到数组的末尾位置，即返回数组的长度。

1
2
3
4
5
6
7
8
class Solution {
    public int searchInsert(int[] nums, int target) {
        for(int i = 0 ; i < nums.length; i ++){
            if(nums[i] >= target) return i; 
        }
        return nums.length;
    }
}

暴力解法(左闭右闭)

1
2
3
4
5
6
7
8
class Solution {
    public int searchInsert(int[] nums, int target) {
        for(int i = 0 ; i <= nums.length - 1; i ++){
            if(nums[i] >= target) return i; 
        }
        return nums.length;
    }
}

二分查找

由于数组已经是非递减排序的，我们可以使用二分查找的思想来加快搜索的过程。具体步骤如下：

  1. 初始化左边界l为数组的第一个元素，右边界r为数组的最后一个元素。
  2. 使用循环不断缩小搜索的范围，直到左右边界相遇：
    • 计算中间索引mid，并取得中间元素值nums[mid]。
    • 如果中间元素值大于目标值，说明目标值在左边，将右边界r更新为mid - 1。
    • 如果中间元素值小于目标值，说明目标值在右边，将左边界l更新为mid + 1。
    • 如果中间元素值等于目标值，直接返回中间索引mid。
  3. 当左右边界相遇时，说明目标值不在数组中，此时左边界即为应该插入的位置，返回左边界即可。

二分(左闭右闭)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int searchInsert(int[] nums, int target) {
        int l =0;
        int r = nums.length -1 ;
        while(l <= r){
            int mid = l + ((r - l) >> 1);
            if(nums[mid] > target){
                r = mid -1 ;
            }else if(nums[mid] < target){
                l = mid + 1;
            }else{
                return mid;
            }
        }
         return r + 1;
    }
}

二分查找法(左闭又开)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int searchInsert(int[] nums, int target) {
        int l =0;
        int r = nums.length ;
        while(l < r){
            int mid = l + ((r - l) >> 1);
            if(nums[mid] > target){
                r = mid;
            }else if(nums[mid] < target){
                l = mid + 1;
            }else{
                return mid;
            }
        }
         return r;
    }
}

复杂度分析

  • 暴力解法的时间复杂度为O(n)，其中n为数组的长度。
  • 二分查找的时间复杂度为O(log n)，因为每次查找都将搜索范围缩小一半。
  • 空间复杂度为O(1)，不需要使用额外的空间。

根据题目要求，我们选择使用二分查找的方法来实现，因为其时间复杂度更低。根据具体的情况，可以选择左闭右闭、左闭右开等方式来实现二分查找。在代码中给出了四种不同的实现方式供参考。

上述是对LeetCode35题目的解题思路和四种解题方法的介绍。通过二分查找的思想，我们可以快速地在非递减排序的数组中查找目标值的位置或应该插入的位置。