【Day 27 】2024-05-04 - 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

[zhiyuanpeng]

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:
                r = mid - 1
            else:
                l = mid + 1
        return 

Time O(logN) space O(1)

[xil324]

    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        left = 0
        right = len(nums)-1
        if target > nums[right]:
            return len(nums)
        if target < nums[left]:
            return 0
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] > target:
                right = mid - 1
            if nums[mid] < target:
                left = mid + 1
            if nums[mid] == target:
                return mid

        return left

[lxy1108]

思路

二分查找

python3代码

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

复杂度分析 时间复杂度o(logn) 空间复杂度o(1)

[Dtjk]

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

[CathyShang]

二分法闭区间

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

• Time O(logn)
• Space O(1)

[atom-set]

思路

使用二分思想

• left = 0 right = nums.length - 1;
• mid = Math.floor((left + right) / 2);
• nums[mid] = target ==> return mid;
• 左侧: nums[mid] < target ==> left = mid + 1;
• 右侧: nums[mid] > target ==> right = mid - 1;
• 返回 left

代码

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function (nums, target) {
  var left = 0;
  var right = nums.length - 1;

  while (left <= right) {
    var mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) {
      return mid;
    }

    if (nums[mid] < target) {
      left = mid + 1;
    }

    if (nums[mid] > target) {
      right = mid - 1;
    }
  }

  return left;
};

复杂度分析

N 为数组规模

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