[Leetcode] Search for a Range 寻找区间

zsirfs 发布于2019-08-14 12:42 / 806人阅读

摘要：二分搜索复杂度时间空间思路其实就是执行两次二分搜索，一次专门找左边边界，一次找右边边界。如果找右边边界，则要判断右边一位的数是否相同。

Search for a Range

Given a sorted array of integers, find the starting and ending position of a given target value.
Your algorithm"s runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
For example, Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4].

二分搜索 复杂度

时间 O(logN) 空间 O(1)

思路

其实就是执行两次二分搜索，一次专门找左边边界，一次找右边边界。特别的，如果找左边边界时，要看mid左边一位的的数是否和当前mid相同，如果相同要继续在左半边二分搜索。如果找右边边界，则要判断右边一位的数是否相同。

代码

public class Solution {
    public int[] searchRange(int[] nums, int target) {
        // 找到左边界
        int front = search(nums, target, "front");
        // 找到右边界
        int rear = search(nums, target, "rear");
        int[] res = {front, rear};
        return res;
    }
    
    public int search(int[] nums, int target, String type){
        int min = 0, max = nums.length - 1;
        while(min <= max){
            int mid = min + (max - min) / 2;
            if(nums[mid] > target){
                max = mid - 1;
            } else if(nums[mid] < target){
                min = mid + 1;
            } else {
                // 对于找左边的情况，要判断左边的数是否重复
                if(type == "front"){
                    if(mid == 0) return 0;
                    if(nums[mid] != nums[mid - 1]) return mid;
                    max = mid - 1;
                } else {
                // 对于找右边的情况，要判断右边的数是否重复
                    if(mid == nums.length - 1) return nums.length - 1;
                    if(nums[mid] != nums[mid + 1]) return mid;
                    min = mid + 1;
                }
            }
        }
        //没找到该数返回-1
        return -1;
    }
}

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64648.html

leetcode 34 Search for a Range

摘要：我们要找出这个目标数字在数组中的存在区间，并以数组形式返回这个区间。要求题目必须在输入数组和目标值返回想法我们需要分别找出最左边的这个元素的位置和最右边的这个元素的位置。由于对于时间的要求，我们在进行查找的时候要采取二分查找。题目详情 Given an array of integers sorted in ascending order, find the starting and...

Awbeci 2019-08-15 14:14 评论0 收藏0
[Leetcode] Missing Ranges 缺失区间

摘要：想象一下假设数组前有一段连续的负无穷到，数组后有一段到正无穷，这样是等价与上下界的。最后循环到停止，当下标为时，我们将当前指针指向，并判断和数组末尾是否能构成最后一个区间。 Missing Ranges Given a sorted integer array where the range of elements are [lower, upper] inclusive, retu...

Gilbertat 2019-08-14 12:36 评论0 收藏0
[Leetcode] Summary Ranges 统计区间

摘要：双层迭代法复杂度时间空间思路外层的循环控制每个的起点，内层的循环控制之内的递增。每当遍历完一个，就把它记录到结果中，并更新下一个的起点。这里的技巧是，判断一个数是否是在内的，只要就行了，即值之差等于下标之差。 Summary Ranges Given a sorted integer array without duplicates, return the summary of it...

Youngdze 2019-08-14 12:33 评论0 收藏0
leetcode34 search for a range

摘要：题目要求即在一个有序排列的数组中，找到目标值所在的起始下标和结束下标。这样一定可以找到目标值的初始下标同理，结合情况和情况，当中间值大于目标值，则将右指针左移至中间，否则将左指针右移至中间，这样一定可以找到目标值的结束下标。题目要求 Given an array of integers sorted in ascending order, find the starting and ...

2shou 2019-08-16 10:32 评论0 收藏0
【LeetCode】贪心算法--划分字母区间（763）

摘要：写在前面今天这篇文章是贪心算法系列的第三篇划分字母区间。前文回顾贪心算法分发糖果刷题汇总汇总贴今日题目字符串由小写字母组成。返回一个表示每个字符串片段的长度的列表。示例输入输出解释划分结果为。每个字母最多出现在一个片段中。写在前面今天这篇文章是贪心算法系列的第三篇--划分字母区间。前文回顾：【LeetCode】贪心算法--分发糖果（135）刷题汇总：【LeetCode】汇总...

honhon 2019-07-31 11:21 评论0 收藏0