Leetcode解题笔记

#35_搜索插入位置

2019-07-19  本文已影响0人  FiveZM

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

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

示例 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
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。



    public static int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            // 上面这行代码可以换成 int mid = (left + right ) / 2;
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            }
        }
        return left;
    }

至于为什么一定得返回左边界 left,我就直接copy了另一个作者的解析

如果返回右边界 right 提交代码不会通过
【注意】下面我尝试说明一下理由,如果你不太理解下面我说的,那是我表达的问题
但我建议你不要纠结这个问题,因为我将要介绍的二分查找法模板,可以避免对返回 left 和 right 的讨论
理由是对于 [1,3,5,6],target = 2,返回大于等于 target 的第 1 个数的索引,此时应该返回 1
在上面的 while (left <= right) 退出循环以后,right < left,right = 0 ,left = 1
根据题意应该返回 left,
如果题目要求你返回小于等于 target 的所有数里最大的那个索引值,应该返回 right

作者:liweiwei1419
链接:https://leetcode-cn.com/problems/two-sum/solution/te-bie-hao-yong-de-er-fen-cha-fa-fa-mo-ban-python-/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


时间复杂度为 o(n²)

    public static int searchInsert(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target)
                return i;
        }
        if (nums.length == 1) {
            if (nums[0] > target)
                return 0;
            return 1;
        }
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[0] > target)
                return 0;
            else if (nums[i] < target && target < nums[i + 1])
                return i + 1;
            else if (i + 2 == nums.length && nums[i + 1] < target) {
                return i + 2;
            }
        }
        return -1;
    }
上一篇 下一篇

猜你喜欢

热点阅读