百度网站下拉怎么做,个人网站建设报价,云主机 怎么做网站,ui设计哪里有培训班题目描述 给定一个已排序的数组 nums 和一个目标值 target#xff0c;你需要找出 target 在数组中的插入位置#xff0c;以保持数组的有序性。如果 target 已经存在于数组中#xff0c;则返回它的索引。 示例
示例 1
输入: nums [1,3,5,6], target 5
输出: 2
解释: 值 5…题目描述 给定一个已排序的数组 nums 和一个目标值 target你需要找出 target 在数组中的插入位置以保持数组的有序性。如果 target 已经存在于数组中则返回它的索引。 示例
示例 1
输入: nums [1,3,5,6], target 5
输出: 2
解释: 值 5 已经存在数组中其索引为 2。示例 2
输入: nums [1,3,5,6], target 2
输出: 1
解释: 值 2 不存在于数组中但当它被插入时将位于 1 和 3 之间因此返回 1。示例 3
输入: nums [1,3,5,6], target 7
输出: 4
解释: 值 7 不存在于数组中当它被插入时将位于数组的末尾因此返回 4。题解
这个问题可以通过二分查找来解决因为数组是已排序的。
初始化设置两个指针 left 和 right 分别指向数组的开始和结束。二分查找在 left 和 right 之间进行二分查找。 ○ 如果 nums[mid] 等于 target则返回 mid。 ○ 如果 nums[mid] 小于 target则将 left 设置为 mid 1。 ○ 如果 nums[mid] 大于 target则将 right 设置为 mid - 1。返回结果如果 target 不在数组中则 left 将指向 target 应该被插入的位置。
代码实现
int searchInsert(vectorint nums, int target) {int left 0, right nums.size() - 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; // 返回插入位置
}复杂度分析
● 时间复杂度O(log n)其中 n 是数组 nums 的长度。这是因为我们使用了二分查找。 ● 空间复杂度O(1)因为我们没有使用额外的空间。 这个算法的优势在于它利用了数组的有序性通过二分查找快速定位目标值的插入位置。
