手机网站 分享按钮,世界500强企业名字,推广之家邀请码,免费看电视剧的网站2021#xff08;一#xff09;问题描述
35. 搜索插入位置 - 力扣#xff08;LeetCode#xff09;35. 搜索插入位置 - 给定一个排序数组和一个目标值#xff0c;在数组中找到目标值#xff0c;并返回其索引。如果目标值不存在于数组中#xff0c;返回它将会被按顺序插入的位…一问题描述
35. 搜索插入位置 - 力扣LeetCode35. 搜索插入位置 - 给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。请必须使用时间复杂度为 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 提示: * 1 nums.length 104 * -104 nums[i] 104 * nums 为 无重复元素 的 升序 排列数组 * -104 target 104https://leetcode.cn/problems/search-insert-position/description/?envTypestudy-plan-v2envIdtop-100-liked
给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 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提示:
1 nums.length 104-104 nums[i] 104nums 为 无重复元素 的 升序 排列数组-104 target 104
二解决思路 这道题和704.二分查找的区别只有target不存在与nums中的情况当target不在nums中是这道题就变成了找数组中第一个大于target的元素。 这里用ans来记录起始值为nums的长度便于处理边缘情况。在取左区间时记录ans而右区间时不记录这是为了统一当target不在nums中时应该取区间的左侧值还是右侧值。这是因为在取左区间且左区间仅包含两个元素时target的插入位置应该取右侧值应该等到left和right相等即区间只剩下一个元素时再取左侧值此时左侧值和右侧值相等在取右区间且右区间仅包含两个元素时target插入位置应该取左侧值。
class Solution {public int searchInsert(int[] nums, int target) {//每次比较的区间包含左右端点int left 0, right nums.length-1,ansnums.length;while(leftright){int mid(leftright)/2;if(targetnums[mid]){return mid;}else if(targetnums[mid]){ansmid;rightmid-1;}else{leftmid1;}}return ans;}
}
