网站开发设计工程师,宝钢工程建设有限公司网站,租服务器,网站建设页面框架题目 给定一个排序数组和一个目标值#xff0c;在数组中找到目标值#xff0c;并返回其索引。
如果目标值不存在于数组中#xff0c;返回它将会被按顺序插入的位置。 示例 示例 1:输入: nums [1,3,5,6], target 5
输出: 2
示例 2:输入: nums [1,3,5,6], target 2
输出: …题目 给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。
如果目标值不存在于数组中返回它将会被按顺序插入的位置。 示例 示例 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 解题思路 方法一首先本题思路找到第一个大于等于target的元素位置即插入位置。所以直接遍历数组找到第一个大于等于target的元素位置就是结果。但本题要求时间复杂度为log(n),那么需要进行优化。方法二二分查找。算法思路将数组分成两份left0mid(left right) / 2rightlength-1。根据mid与target的大小进一步划分区域。如果midtarget说明target在0到mid之间。反之在mid到length-1之间。将范围缩小(left mid 1 或 right mid - 1 ), 继续比较。本题可以用二分查找的思想不过算法是查找相等数据本题需要查找第一个大于等于的数据。 这里说明下为什么以left进行返回 本题结果即找到第一个大于等于target的元素。在二分查找的过程中遇到的第一个mid对应元素大于target时mid对应的元素不一定是第一个大于target元素只是二分查找过程中遇到的第一个。此时需要继续缩小范围就继续比较。 那么什么情况下是第一个呢首先mid对应元素和target相等的时候直接返回mid位置即插入位置。大于的情况因为数组中不存在target那么一定会遍历到leftrightmid的时候如果这个元素大于target根据二分查找算法原理此时right mid - 1leftright跳出循环left即结果;如果这个元素小于targetleft mid1leftright跳出循环left即结果(已经加1)。这里不管是大于还是小于mid的其他位置都是已经确认了大于或小于target了。那么如果这个位置小于target那么它后面的就是第一个大于target的如果这个位置大于target那么他就是第一个大于target的。代码(Java) // 方法一
class Solution {public int searchInsert(int[] nums, int target) {if (nums null || nums.length 0) {return -1;}if (nums[0] target) {return 0;}if (nums[nums.length - 1] target) {return nums.length;}for (int i 0; i nums.length; i) {if (nums[i] target) {return i;}}return nums.length;}
} // 方法二
class Solution {public int searchInsert(int[] nums, int target) {if (nums null || nums.length 0) {return -1;}if (nums[0] target) {return 0;}if (nums[nums.length - 1] target) {return nums.length;}int left 0;int right nums.length - 1;while (left right) {int mid (left right) / 2;if (nums[mid] target) {return mid;} else if (nums[mid] target) {left mid 1;} else {right mid - 1;}}return left;}
}
