LeetCode-简单-35-搜索插入位置(Java)

气死了,原本今天做的是中等难度的第二十九题两数相除,但力扣这编译器太气人了,不溢出不越界,在那里一直循环,加条件中断也不管不顾,我编译器都正常输出,测试都测试不了,INT_MAX次运算输出他们又显示不全,气死了。

就换了个简单的题目放松一下。

不得不说,在这些基础函数的使用上,java和c真的是无缝切换。

题目

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:

输入: [1,3,5,6], 5
输出: 2
示例 2:

输入: [1,3,5,6], 2
输出: 1
示例 3:

输入: [1,3,5,6], 7
输出: 4
示例 4:

输入: [1,3,5,6], 0
输出: 0

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/search-insert-position
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

用的二分法,因为给的数组是排序好的。
当然,没排序好我们也可以把他排序好再算。

先设立两个位置,searchLeftSite与searchRightSite(下面简称lSite与rSite),表示本次查找区间的左边和右边界限,初始值为0和数组长度。

每次循环,将target与区间中间数比较:

如果相等,则找到了target,输出中间位置。

如果target更大,要分两钟情况:
区间长度=1,此时直接输出右边界即可,原因见下面补充说明1
区间长度>1,此时将左边界增加一半的区间长度。

如果target更小,要分两钟情况:
区间长度=1,直接输出左边界
区间长度>1,将右边界减少一半区间长度。

补充说明1:
实际比较时,代码取得区间中间数是nums[(lSite+rSite)/2],如果target不在nums数组中,那么最终一定会出现这么一个结果:
nums[lSite] < target < nums[rSite],此时rSite = lSite+1。
此时target比较的对象nums[lSite+rSite],可以写作nums[ (lSite*2 +1)/2 ],即nums[lSite],
因此,target与nums[lSite+rSite]的比较,实际上是target与nums[lSite]的比较,
所以,如果target更大,则取rSite作为输出,反之则取lSite作为输出。

补充说明2:
根据题目的要求,有三种特殊情况要先判断,
一种是target<=nums[0],一种是target==nums[nums.length-1],一种是target>nums[nums.length-1],
直接当成特殊情况处理就好了,因为根据题目要求的不同,三种情况(实际是四种,但本体中有两种情况操作相同)的处理方式都可能不同。

代码

class Solution {
    public int searchInsert(int[] nums, int target) {
        int searchRightSite = nums.length;
        int searchLeftSite = 0;
        int temp;

        if(nums[0]>=target) return 0;
        else if(nums[nums.length-1]<target) return nums.length;
        else if(nums[nums.length-1]==target) return nums.length-1;

        while(true){
            temp = (searchRightSite+searchLeftSite)/2;
            if(target == nums[temp]) return temp;
            else if(target >  nums[temp]){
                if(searchLeftSite+1 == searchRightSite) return searchRightSite;
                searchLeftSite += (searchRightSite-searchLeftSite)/2;
            }
            else{
                if(searchLeftSite+1 == searchRightSite) return searchLeftSite;
                searchRightSite -= (searchRightSite-searchLeftSite)/2;
            }
        }
    }
}

You may also like...

发表评论

邮箱地址不会被公开。 必填项已用*标注