开发者

Go语言题解LeetCode35搜索插入位置示例详解

开发者 https://www.devze.com 2022-12-31 10:54 出处:网络 作者: 刘09k11
目录题目描述思路分析AC 代码总结优先考虑边界情况 红蓝标记解法代码题目描述
目录
  • 题目描述
    • 思路分析
    • AC 代码
  • 总结
    • 优先考虑边界情况 红蓝标记解法
      • 代码

    题目描述

    原题链接 :

    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,python进行相应的下标返回

    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 searchwww.devze.comInsert(int* nums, int numsSize, int target){
        if(nums[0]>=target)
        {
            return 0;
        }
        else if(nums[numsSize-1]<target)
        {
             return numsSize;
        }
        e开发者_JAVA教程lse if(nums[numsSize-1]==target)
        {
            return nums编程客栈Size-1;
        }
        else{
             int r=numsSize-1;
             int i=0;
        while(i+1!=r)
    js    {
            int mid=(i+r)/2;
        if(nums[mid]>target )
    {
        r=mid;
    }
            else if(nums[mid]<target)
                     i=mid;
            else{
                     return mid;
     }
        }
                return i+1;
    
        }
    }

    以上就是Go语言题解LeetCode35搜索插入位置示例详解的详细内容,更多关于Go语言搜索插入位置的资料请关注我们其它相关文章!

    0

    精彩评论

    暂无评论...
    验证码 换一张
    取 消

    关注公众号