LeetCode-35. Search Insert Position | 搜索插入位置

题目

LeetCode
LeetCode-cn

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

Example 1:
Input: nums = [1,3,5,6], target = 5
Output: 2

Example 2:
Input: nums = [1,3,5,6], target = 2
Output: 1

Example 3:
Input: nums = [1,3,5,6], target = 7
Output: 4

Example 4:
Input: nums = [1,3,5,6], target = 0
Output: 0

Example 5:
Input: nums = [1], target = 0
Output: 0
 
Constraints:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums contains distinct values sorted in ascending order.
-104 <= target <= 104

题解

题目为简单难度。

解法一：暴力求解法

使用for循环遍历nums数组，从下标0开始按个与目标值target进行对比，如果nums[i]>=target，说明目标值在数组所有元素之前，直接返回i即可；另一种情况就是目标值在数组所有元素之后，这时返回nums数组长度len(nums)即可。

//Go
func searchInsert(nums []int, target int) int {
    for i := 0;i <len(nums);i++ {
        if nums[i] >= target {
            return i
        }
    }
    
    return len(nums)
}

执行结果：

leetcode：
Runtime: 4 ms, faster than 88.29% of Go online submissions for Search Insert Position.
Memory Usage: 3.1 MB, less than 100.00% of Go online submissions for Search Insert Position.

leetcode-cn：
执行用时：4 ms, 在所有 Go 提交中击败了90.15%的用户
内存消耗：2.9 MB, 在所有 Go 提交中击败了100.00%的用户

解法二：二分查找法

//Go
func searchInsert(nums []int, target int) int {
    low := 0
    high := len(nums) - 1
    for low <= high {
        // 下方写法为了防止数据溢出，如果先加在除以2 加完的值可能会大于INT_MAX，造成溢出 
        mid := low + (high - low) / 2
        guess := nums[mid]
        if guess == target {
            return mid //找到了，返回下标
        }
        if guess > target {
            high = mid - 1
        } else {
            low = mid +1
        }
    }

    return low //没找到
}

执行结果：

leetcode-cn：
执行用时：4 ms, 在所有 Go 提交中击败了90.15%的用户
内存消耗：3 MB, 在所有 Go 提交中击败了56.60%的用户

leetcode：
Runtime: 8 ms, faster than 8.78% of Go online submissions for Search Insert Position.
Memory Usage: 3.3 MB, less than 6.08% of Go online submissions for Search Insert Position.

解法三：golang-sort.SearchInts包

解题时不推荐。

//Go
func searchInsert(nums []int, target int) int {
    return sort.SearchInts(nums, target)
}

执行结果：

leetcode：
Runtime: 4 ms, faster than 88.29% of Go online submissions for Search Insert Position.
Memory Usage: 3.1 MB, less than 100.00% of Go online submissions for Search Insert Position.

leetcode-cn：
执行用时：4 ms, 在所有 Go 提交中击败了90.15%的用户
内存消耗：3 MB, 在所有 Go 提交中击败了56.60%的用户