Go语言题解LeetCode35搜索插入位置示例详解
刘09k11 人气:0题目描述
原题链接 :
35. 搜索插入位置 - 力扣（LeetCode） (leetcode-cn.com)
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 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 <= 10^4
-10^4 <= nums[i] <= 10^4
nums 为 无重复元素 的 升序 排列数组
-10^4 <= target <= 10^4
思路分析
首先明确题目的含义：
（1）数组是有序的；
（2）如果含有与目标值相等，则返回目标值下标，若不同，则按顺序排序获取下标
思路：采用二分搜索法的策略，获取中间数据的大小，缩短数组的大小定位区间，如在数组中间的前一段，数组中间的后一段
获取下标i的值arrs[i]>=target,进行相应的下标返回
AC 代码
class Solution {
public int searchInsert(int[] nums, int target) {
int index = (nums.length / 2);
if (nums[index] >= target) {
return compareByIndex(nums, 0, index+1, target);
} else
return compareByIndex(nums, index+1, nums.length, target);
}
private int compareByIndex(int[] nums, int start, int end, int target) {
for (int i = start; i < end; i++) {
if (nums[i] >= target) {
return i;
}
}
return end;
}
}
总结
这种查找位置的，肯定二分法是合适的，即使不能直接套用二分法的公式，也是二分法的思想，变种。
参考
❤️思维导图整理: 总结了二分查找的通用模板写法, 彻底解决几个易混淆问题❤️ - 搜索插入位置
优先考虑边界情况 红蓝标记解法
首先考虑target是否>=nums[numsSize-1],大于则返回numsSize，等于则返回numsSize-1;
再检查底线，若小于等于nums[0]则返回nums[0]；
else
定义左边界left=0，右边界right=numsSize-1；
进入循环，缩小边界，直到left+1=right；
若找到则直接返回，循环结束时未找到则返回left+1（在left与right之间）
代码
int searchInsert(int* nums, int numsSize, int target){
if(nums[0]>=target)
{
return 0;
}
else if(nums[numsSize-1]<target)
{
return numsSize;
}
else if(nums[numsSize-1]==target)
{
return numsSize-1;
}
else{
int r=numsSize-1;
int i=0;
while(i+1!=r)
{
int mid=(i+r)/2;
if(nums[mid]>target )
{
r=mid;
}
else if(nums[mid]<target)
i=mid;
else{
return mid;
}
}
return i+1;
}
}加载全部内容