【Day 27 】2021-10-06 - 35. 搜索插入位置

[azl397985856]

35. 搜索插入位置

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/search-insert-position

前置知识

暂无

题目描述

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

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

示例 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

[xy147]

思路

遍历

js代码

var searchInsert = function (nums, target) {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] >= target) {
      return i;
    }
  }
  return nums.length;
};

复杂度分析

• 时间复杂度: O(n)
• 空间复杂度: O(1)

[shixinlovey1314]

Title:35. Search Insert Position

Question Reference LeetCode

Solution

Binary Search, when low > high, low is the postion to insert.

Code

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int l = 0, r = nums.size() -1;
        
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target)
                return mid;
            else if (target > nums[mid])
                l = mid + 1;
            else 
                r = mid - 1;
        }
        
        return l;
    }
};

Complexity

Time Complexity and Explanation

O(logn)

Space Complexity and Explanation

O(1)

[yanglr]

思路:

题意：由于题中原数组是从小到大升序排列，故只需找到第一个≥ target的数。

方法: 二分搜索

一开始就提到了题意是由于题中原数组是从小到大升序排列，故需找到第一个≥ target的数。

故二分搜索的目标是：二分出>= target 第一个位置。

check(mid)对应的性质是:

x >= target

假如mid位置的数x满足 x >= target，那么分界点就在mid 的左边，且M 有可能是分界点。

此时右侧区间 [M, R] 是完全满足这个性质的，故可以放心地调整：R = mid,

那么我们可以选择acwing模板1，配套地，L自然需要调整为 mid +1。

// 模板1: 需调整 r = mid
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid))
            r = mid;
        // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}

代码

实现语言: C++

实现方式1:

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        if (nums.back() < target) return nums.size();  /* 这种情况需要特判 */
        int L = 0, R = nums.size() - 1;
        while (L < R)
        {
            int mid = (L+R)/2;
            if (nums[mid] >= target)
                R = mid;
            else L = mid + 1;
        }
        return L;
    }
};

注意要进行特殊边界的处理，题意: 1 ≤ nums.length ≤ 10^4， 故不需考虑原数组为空的情况。

但有可能出现原数组最大的数都比 target 小的情况，所以需要一开始就特殊处理这种情况。

实现方式2:

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int L = 0, R = nums.size() - 1;
        while (L < R)
        {
            int mid = (L+R)/2;
            if (nums[mid] >= target)
                R = mid;
            else L = mid + 1;
        }
        return (nums[L] >= target) ? L : L + 1;
    }
};

复杂度分析:

• 时间复杂度: O(N logN)
• 空间复杂度: O(1)

[xingzhan0312]

var searchInsert = function (nums, target) {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] >= target) {
      return i;
    }
  }
  return nums.length;
};

[BpointA]

思路

二分法找位置。边界处理：在右边界放一个正无穷的数，即可判断右边界。所有位置都无法放下的，则说明其小于所有数，放在左边界。

Python3代码

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left=0
        right=len(nums)-1
        nums.append(float("inf"))
        
        while left<=right:
            mid=(left+right)//2
            if nums[mid]==target:
                return mid
            elif nums[mid]<target and nums[mid+1]>=target:
                return mid+1
            elif nums[mid]<target:
                left=mid+1
            else:
                right=mid-1
        return 0
           
           
        

复杂度

时间复杂度：O(logn)，二分法

空间复杂度：O(1)，两个指针

[kidexp]

thoughts

二分法 把问题等价于找到第一个大于等于这个数

code

class Solution:

    def searchInsert(self, nums: List[int], target: int) -> int:
        """
        classic binary search
        """
        if not nums:
            return 0
        start, end = 0, len(nums)-1
        while start <= end:
            mid = (start + end) // 2
            if nums[mid] < target:
                start = mid + 1
            elif nums[mid] > target:
                end = mid - 1
            else:
                return mid
        return start

complexity

时间复杂度O(lgn)

空间复杂度O(1)

[mayqiu]

class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1

    while left <= right:
        middle = (left + right) // 2

        if nums[middle] < target:
            left = middle + 1
        elif nums[middle] > target:
            right = middle - 1
        else:
            return middle
    return right + 1

[thinkfurther]

思路

二分查找

代码

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        
        while(left<=right):
            middle = (left+right)//2
            if nums[middle] == target:
                return middle
            if nums[middle] < target:
                left = middle + 1
            else:
                right = middle - 1
                
        return left

复杂度

时间复杂度 ：O(log N)

空间复杂度：O(1)

[pophy]

思路

• 2分查找 直接套用模板

Java Code

    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                right  = mid;
            } else {
                left = mid;
            }               
        }     
        if (target <= nums[left]) {
            return left;
        }       
        if (target <= nums[right]) {
            return right;
        }
        return right + 1;
    }

时间&空间

• 时间 O(log(n))
• 空间 O(1)

[JiangyanLiNEU]

Binary search: runtime=O(nlogn), space = O(1)

JavaScript Code

var searchInsert = function(nums, target) {
    let left = 0;
    let right = nums.length-1;
    let remain = (left+right)%2
    let middle = (left+right-remain)/2
    
    if (target <= nums[left]){
        return left;
    }else if (target == nums[right]){
        return right;
    }else if (target > nums[right]){
        return right+1;
    }else{
        while (left<right){
            if (nums[middle]==target){
                return middle;
            }else if (nums[middle]>target){
                right = middle;
            }else if (nums[middle]<target){
                left = middle+1;
            };
            remain = (left+right)%2
            middle = (left+right-remain)/2
        };
        return left;
    }

Python Code

class Solution(object):
    def searchInsert(self, nums, target):
        left = 0
        right = len(nums)-1
        if target<= nums[left]:
            return left
        if target>=nums[right]:
            if target == nums[right]:
                return right
            else:
                return right+1
        middle = (left+right)//2
        while left<right:
            if nums[middle] == target:
                return middle
            elif nums[middle] > target:
                right = middle
            elif nums[middle] < target:
                left = middle +1 
            middle = (left+right)//2
        return left
```

[yachtcoder]

bisect_left.
O(lgn), O(1).

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums)-1
        while l <= r:
            mid = (l+r)//2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                l = mid + 1
            else:
                r = mid - 1
        return l

[zliu1413]

binary search: runtime = O(logN), space = O(1)

class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
l,r = 0,len(nums)
while l<r:
mid = (l+r)//2
if nums[mid] == target:
return mid
elif nums[mid] < target:
l = mid+1
else:
r = mid
return r