成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

leetcode34 search for a range

2shou / 2885人閱讀

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

題目要求 
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].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

即 在一個有序排列的數(shù)組中，找到目標值所在的起始下標和結(jié)束下標。如果該目標值不在數(shù)組中，則返回[-1,-1]
題目中有一個特殊要求是時間復(fù)雜度為O(logn),也就是在暗示我們，不能只是單純的按照順序遍歷數(shù)組，要盡量減去無效遍歷。所以這題的核心思路為二分法遍歷。

思路一 二分法初級運用

最初的思路是使用二分法找到目標值的其中一個下標，再根據(jù)該下標左右遍歷得出初始下標和結(jié)束下標。

    public int[] searchRange(int[] nums, int target) {
        int[] result = new int[]{-1, -1};
        int left = 0;
        int right = nums.length-1;
        while(left<=right){
            int mid = (left + right)/2;
            if(nums[mid]==target){
                while(mid>=left && nums[mid]==target){
                    mid--;
                }
                result[0] = mid+1;
                mid = (left + right)/2;
                while(mid<=right && nums[mid]==target){
                    mid++;
                }
                result[1] = mid - 1;
                break;
            }else if (nums[mid] > target){
                right = mid-1;
            }else{
                left = mid+1;
            }
        }
        return result;
    }
思路二：二分法分別運用

假設(shè)我們目前有左指針，右指針，并判斷中間值和目標值之間的關(guān)系，那么一共有三種關(guān)系情況

中間值小于目標值，則目標值只可能在右子數(shù)組

中間值大于目標值，則目標值只可能在左子數(shù)組

中間值等于目標值，則目標值在左右子數(shù)組都可能存在

結(jié)合情況1和情況3，當中間值小于目標值，則將左指針右移至中間，否則將右指針左移至中間。這樣一定可以找到目標值的初始下標
同理，結(jié)合情況2和情況3，當中間值大于目標值，則將右指針左移至中間，否則將左指針右移至中間，這樣一定可以找到目標值的結(jié)束下標。

    public int[] searchRange2(int[] nums, int target) {
        int[] range = new int[]{nums.length, -1};
        searchRange2(nums, target, 0, nums.length, range);
        if(range[0]>range[1]) range[0]=-1;
        return range;
    }
    public void searchRange2(int[] nums, int target, int left, int right, int[] range){
        if(left>right) return;
        int mid = ( left + right ) / 2;
        if(nums[mid] == target){
            if(mid < range[0]){
                range[0] = mid;
                searchRange2(nums, target,left, mid-1, range);
            }
            if(mid > range[1]){
                range[1] = mid;
                searchRange2(nums, target, mid+1, right, range);
            }
        }else if (nums[mid]

這種思路更清晰的代碼表示如下


    public int[] searchRange3(int[] nums, int target) {
        int[] result = new int[2];
        result[0] = findFirst(nums, target);
        result[1] = findLast(nums, target);
        return result;
    }

    private int findFirst(int[] nums, int target){
        int idx = -1;
        int start = 0;
        int end = nums.length - 1;
        while(start <= end){
            int mid = (start + end) / 2;
            if(nums[mid] >= target){
                end = mid - 1;
            }else{
                start = mid + 1;
            }
            if(nums[mid] == target) idx = mid;
        }
        return idx;
    }

    private int findLast(int[] nums, int target){
        int idx = -1;
        int start = 0;
        int end = nums.length - 1;
        while(start <= end){
            int mid = (start + end) / 2;
            if(nums[mid] <= target){
                start = mid + 1;
            }else{
                end = mid - 1;
            }
            if(nums[mid] == target) idx = mid;
        }
        return idx;
    }



想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~

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

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/69966.html

相關(guān)文章

  • leetcode 34 Search for a Range

    摘要：我們要找出這個目標數(shù)字在數(shù)組中的存在區(qū)間，并以數(shù)組形式返回這個區(qū)間。要求題目必須在輸入數(shù)組和目標值返回想法我們需要分別找出最左邊的這個元素的位置和最右邊的這個元素的位置。由于對于時間的要求，我們在進行查找的時候要采取二分查找。 題目詳情 Given an array of integers sorted in ascending order, find the starting and...

    Awbeci 評論0 收藏0

  • [Leetcode] Search for a Range 尋找區(qū)間

    摘要：二分搜索復(fù)雜度時間空間思路其實就是執(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 評論0 收藏0

  • leetcode 部分解答索引（持續(xù)更新～）

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

    leo108 評論0 收藏0

  • [LintCode/LeetCode] Search for a Range [左右邊界法/一次循環(huán)

    摘要：首先，建立二元結(jié)果數(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 評論0 收藏0

  • 【Leetcode刷題】第 35 題：Search Insert Position 搜索插入位置——

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

    haobowd 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<