电子商务网站开发数据库表格国家最新新闻

LeetCode 35.搜索插入位置

题目描述

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

请必须使用 O(log n) 的时间复杂度来实现。

示例 1:

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

示例 2:

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

示例 3:

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

示例 4:

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

Java 实现代码

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

解题思路

1. 二分查找： 由于题目要求时间复杂度为 O(log n)，可以使用二分查找算法。通过不断缩小查找区间，确定目标值的位置或其插入位置。

2. 算法步骤：

   • 初始化 left 和 right 指针，分别指向数组的起始和结束位置。
   • 计算中间位置 mid。
   • 判断 nums[mid] 是否等于目标值：
     • 如果等于，直接返回 mid。
     • 如果小于目标值，移动左指针 left = mid + 1。
     • 如果大于目标值，移动右指针 right = mid - 1。
   • 最终，当 left > right 时，返回 left 作为目标值的插入位置。

复杂度分析

• 时间复杂度：O(log n)，其中 n 是数组的长度。二分查找每次都将搜索范围减半，因此时间复杂度是对数级别的。
• 空间复杂度：O(1)。我们只使用了常量级别的额外空间来存储指针和中间变量。

执行过程示例

以 nums = [1,3,5,6]，target = 2 为例：

1. 初始化：left = 0, right = 3
2. 第一次迭代：
   • 计算 mid = 1 ((0 + 3) / 2)
   • 比较 nums[mid] = 3 和 target = 2
   • nums[mid] > target，移动右指针：right = mid - 1 = 0
3. 第二次迭代：
   • 计算 mid = 0 ((0 + 0) / 2)
   • 比较 nums[mid] = 1 和 target = 2
   • nums[mid] < target，移动左指针：left = mid + 1 = 1
4. 退出循环，返回 left = 1，即插入位置。