ShowDocs
搜索文章Ctrl K

外观

← 返回算法列表
算法推演

Leetcode 数组 · 搜索插入位置至完整入口与预期结果 ​

返回分篇目录

搜索插入位置 ​

用 [1,3,5,6]、目标 2 推演，插入位置应在 1 与 3 之间，即下标 1。按下方闭区间实现，初始 ans=4；遇到不小于目标的中点先记为候选，再继续往左找。没有相等元素仍可返回插入点；若目标大于全部元素，ans 保持为数组长度。

查看图表代码

  • 题目连接

  • 题目说明

    • 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
    • 请必须使用时间复杂度为 O(log n) 的算法。

  • 示例 1:

    shell
    输入: nums = [1,3,5,6], target = 5
输出: 2

  • 示例 2:

    shell
    输入: nums = [1,3,5,6], target = 2
输出: 1

  • 示例 3:

    shell
    输入: nums = [1,3,5,6], target = 7
输出: 4

  • 提示:

    • 1 <= nums.length <= 10^4
    • -10^4 <= nums[i] <= 10^4
    • nums 为 无重复元素的 升序排列数组
    • -10^4 <= target <= 10^4

  • 题目

    text
    func searchInsert(nums []int, target int) int {

}

提示：先逐步手算索引、读写位置或进位，再展开实现。

参考实现与分析

  • 解题

    go
      func searchInsert(nums []int, target int) int {
    if len(nums) == 0 {
      return 0
    }

    n := len(nums)
    ans := n
    left, right := 0, n-1

    for left <= right {
      mid := (right-left)>>1 + left
      if target <= nums[mid] {
        ans = mid
        right = mid - 1
      } else {
        left = mid + 1
      }

    }
    return ans
  }

加一 ​

[1,9,9] 从最右位加一，两次把 9 变为 0 并向左进位，最后把 1 变为 2，得到 [2,0,0]。遇到非 9 的位加一即可返回；只有所有位都是 9，才需要额外的最高位，例如 [9,9]→[1,0,0]。逐位操作避免把整个数组转成可能溢出的整数。

查看图表代码

  • 题目连接

  • 题目说明

    • 给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

    • 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

    • 你可以假设除了整数 0 之外，这个整数不会以零开头。

    • 示例

      • 1
      shell
        输入：digits = [1,2,3]
  输出：[1,2,4]
  解释：输入数组表示数字 123。
      • 2
      shell
        输入：digits = [4,3,2,1]
  输出：[4,3,2,2]
  解释：输入数组表示数字 4321。
      • 3
      shell
          输入：digits = [0]
    输出：[1]

    • 提示

      shell
        1 <= digits.length <= 100
  0 <= digits[i] <= 9

  • 题目

    text
    func plusOne(digits []int) []int {
}

提示：先逐步手算索引、读写位置或进位，再展开实现。

参考实现与分析

  • 解题

    • 情况 1

      • 如果输入

        • [8,9,9] -> [9,0,0]

      • 思路:

        • 倒序查看元素是否不等 9
        • 当遍历到 8 时候,会把 8++
        • 然后遍历 8 后面所有的元素,后面元素全部修改为 0
        • 返回即可

  • 情况 2

    • 如果输入

      • [9,9,9] -> [1,0,0,0]
      • [9] -> [1,0]

    • 思路

      • 再循环中只要不能 9 就直接跳过了
      • 再下面直接增加数组然后直接第一个 index 改为 1 即可

  • 解题

    go
      func plusOne(digits []int) []int {

    for i := len(digits) - 1; i >= 0; i-- {
      if digits[i] != 9 {
        digits[i]++

        for j := i + 1; j < len(digits); j++ {
          digits[j] = 0
        }
        return digits
      }
    }

    r := make([]int, len(digits)+1)
    r[0] = 1
    return r
  }

完整入口与预期结果 ​

上文空函数是供填写的题目模板，后面的函数各是解法片段；同名解法只选择一个，不可把所有块拼接成同一包。判题伪代码不作为Go源文件。以下独立项目含完整模块与main入口，单一文件复用五个题目的实现；无需复制题目模板，未执行或编译：

text
module showdocs.example/array-practice

go 1.27.0
go
// Standalone standard-library teaching example; not executed by site checks.
package main

import "fmt"

func twoSum(nums []int, target int) []int {
    seen := make(map[int]int)
    for i, value := range nums {
        if j, ok := seen[target-value]; ok { return []int{j, i} }
        seen[value] = i
    }
    return nil
}

func removeDuplicates(nums []int) int {
    if len(nums) == 0 { return 0 }
    slow := 1
    for fast := 1; fast < len(nums); fast++ {
        if nums[fast] != nums[slow-1] {
            nums[slow] = nums[fast]
            slow++
        }
    }
    return slow
}

func removeElement(nums []int, value int) int {
    left, right := 0, len(nums)
    for left < right {
        if nums[left] == value {
            nums[left] = nums[right-1]
            right--
        } else { left++ }
    }
    return left
}

func searchInsert(nums []int, target int) int {
    left, right := 0, len(nums)
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] < target { left = mid+1 } else { right = mid }
    }
    return left
}

func plusOne(digits []int) []int {
    // Precondition: a nonempty decimal representation; digits are in 0..9.
    for i := len(digits)-1; i >= 0; i-- {
        if digits[i] < 9 { digits[i]++; return digits }
        digits[i] = 0
    }
    out := make([]int, len(digits)+1)
    out[0] = 1
    return out
}

func main() {
    fmt.Println(twoSum([]int{2, 7, 11, 15}, 9))
    sorted := []int{1, 1, 2}
    k := removeDuplicates(sorted)
    fmt.Println(k, sorted[:k])
    values := []int{3, 2, 2, 3}
    k = removeElement(values, 3)
    fmt.Println(k, values[:k])
    fmt.Println(searchInsert([]int{1, 3, 5, 6}, 2))
    fmt.Println(plusOne([]int{9, 9}))
}

从该独立目录理解go run .的操作，预期依次是[0 1]、2 [1 2]、2 [2 2]、1、[1 0 0]。twoSum预期平均O(n)时间/O(n)额外空间；有序去重和双指针移除O(n)/O(1)，原移除方法一反复搬移最坏O(n²)；二分O(log n)/O(1)，加一O(n)最坏时间且全9需要新结果数组。输入范围沿用题目：不存在答案返回nil只用于twoSum的扩展边界，任意大int溢出不在题目值域内。

边界自检参考答案

[3,3]目标6必须用两个不同下标；nil有序去重与空切片移除均返回0；空输入的插入位置为0；[9,9]加一为[1,0,0]。修改后的有效前缀才是移除/去重结果，尾部不作断言。不能以输出整个原切片未缩短认定错误。

继续阅读