leetcode 34 Search for a Range

Awbeci 發(fā)布于2019-08-15 14:14 / 2219人閱讀

摘要：我們要找出這個目標數(shù)字在數(shù)組中的存在區(qū)間，并以數(shù)組形式返回這個區(qū)間。要求題目必須在輸入數(shù)組和目標值返回想法我們需要分別找出最左邊的這個元素的位置和最右邊的這個元素的位置。由于對于時間的要求，我們在進行查找的時候要采取二分查找。

題目詳情

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].題目的意思是，輸入一個升序排列的整數(shù)數(shù)組和一個目標值。我們要找出這個目標數(shù)字在數(shù)組中的存在區(qū)間，并以數(shù)組形式返回這個區(qū)間。如果這個數(shù)字不存在于數(shù)組之中，則返回｛－1.－1｝。要求題目必須在O(logn)
For example,
輸入數(shù)組[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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://systransis.cn/yun/68489.html

leetcode34 search for a range

摘要：題目要求即在一個有序排列的數(shù)組中，找到目標值所在的起始下標和結束下標。這樣一定可以找到目標值的初始下標同理，結合情況和情況，當中間值大于目標值，則將右指針左移至中間，否則將左指針右移至中間，這樣一定可以找到目標值的結束下標。題目要求 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 尋找區(qū)間

摘要：二分搜索復雜度時間空間思路其實就是執(zhí)行兩次二分搜索，一次專門找左邊邊界，一次找右邊邊界。如果找右邊邊界，則要判斷右邊一位的數(shù)是否相同。 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 部分解答索引（持續(xù)更新～）

摘要：前言從開始寫相關的博客到現(xiàn)在也蠻多篇了。而且當時也沒有按順序寫現(xiàn)在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖?。所以在這里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言從開始寫leetcode相關的博客到現(xiàn)在也蠻多篇了。而且當時也沒有按順序寫～現(xiàn)在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖?。所以在這里做個索引嘻嘻。順序整理 1~50 1...

leo108 2019-08-15 14:26 評論0 收藏0
[LintCode/LeetCode] Search for a Range [左右邊界法/一次循環(huán)

摘要：首先，建立二元結果數(shù)組，起點，終點。二分法求左邊界當中點小于，移向中點，否則移向中點先判斷起點，再判斷終點是否等于，如果是，賦值給。 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 搜索插入位置——

摘要：如果目標值不存在于數(shù)組中，返回它將會被按順序插入的位置。因此需要關注這些測試用例，在單機上逐個測試成功后再提交。因為題目中只要求返回索引，并不要求插到數(shù)組中，所以應該說又簡化了一些，是一道簡單題目。爭取在下一篇給出優(yōu)化解法。「 Leetcode刷題」系列，僅為刷題過程中對于算法和編程的思考與記錄，如果對你有幫助歡迎點贊收藏。博主也在探索刷題過程中，記錄的一些知識點可能很小白，因此主...

haobowd 2019-07-31 11:17 評論0 收藏0