leetcode 34 Search for a Range

Awbeci 发布于2019-08-15 14:14 / 2133人阅读

摘要：我们要找出这个目标数字在数组中的存在区间，并以数组形式返回这个区间。要求题目必须在输入数组和目标值返回想法我们需要分别找出最左边的这个元素的位置和最右边的这个元素的位置。由于对于时间的要求，我们在进行查找的时候要采取二分查找。

题目详情

Given an array of integers sorted in ascending order, 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].题目的意思是，输入一个升序排列的整数数组和一个目标值。我们要找出这个目标数字在数组中的存在区间，并以数组形式返回这个区间。如果这个数字不存在于数组之中，则返回｛－1.－1｝。要求题目必须在O(logn)
For example,
输入数组[5, 7, 7, 8, 8, 10]和目标值8,
返回[3, 4].

想法

我们需要分别找出最左边的这个元素的位置、和最右边的这个元素的位置。

由于对于时间的要求，我们在进行查找的时候要采取二分查找。

需要注意的是，对于寻找左边界的时候，如果nums[i]等于target值，也要将mid赋值为高位指针high，以找到最左边的等于target的元素。

解法

    public int[] searchRange(int[] nums, int target) {
        int[] res = {-1,-1};
        int leftIndex = findIndex(nums,target,true);
        if(leftIndex == nums.length || nums[leftIndex] != target){
            return res;
        }
        
        res[0] = leftIndex;
        res[1] = findIndex(nums,target,false)-1;
        
        return res;
    }
    public int findIndex(int[] nums,int target,boolean left){
        int low = 0;
        int high = nums.length;
        
        while(low < high){
            int mid = (low + high)/2;
            if(nums[mid] > target ||(left && target == nums[mid])){
                high = mid;
            }else{
                low = mid +1;
            }
        }       
        return low;
    }

云服务器 GPU云服务器阿里云34元轻量服务器2T Leetcod LeetCode vps34

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

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

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] Search for a Range 寻找区间

摘要：二分搜索复杂度时间空间思路其实就是执行两次二分搜索，一次专门找左边边界，一次找右边边界。如果找右边边界，则要判断右边一位的数是否相同。 Search for a Range Given a sorted array of integers, find the starting and ending position of a given target value. Your algo...

zsirfs 2019-08-14 12:42 评论0 收藏0
leetcode 部分解答索引（持续更新～）

摘要：前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写～现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理 1~50 1...

leo108 2019-08-15 14:26 评论0 收藏0
[LintCode/LeetCode] Search for a Range [左右边界法/一次循环

摘要：首先，建立二元结果数组，起点，终点。二分法求左边界当中点小于，移向中点，否则移向中点先判断起点，再判断终点是否等于，如果是，赋值给。 Problem Given a sorted array of n integers, find the starting and ending position of a given target value. If the target is not...

zhangrxiang 2019-08-14 15:41 评论0 收藏0
【Leetcode刷题】第 35 题：Search Insert Position 搜索插入位置——

摘要：如果目标值不存在于数组中，返回它将会被按顺序插入的位置。因此需要关注这些测试用例，在单机上逐个测试成功后再提交。因为题目中只要求返回索引，并不要求插到数组中，所以应该说又简化了一些，是一道简单题目。争取在下一篇给出优化解法。「 Leetcode刷题」系列，仅为刷题过程中对于算法和编程的思考与记录，如果对你有帮助欢迎点赞收藏。博主也在探索刷题过程中，记录的一些知识点可能很小白，因此主...

haobowd 2019-07-31 11:17 评论0 收藏0