亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專(zhuān)欄INFORMATION COLUMN

leetcode 34 Search for a Range

Awbeci / 2279人閱讀

摘要：我們要找出這個(gè)目標(biāo)數(shù)字在數(shù)組中的存在區(qū)間，并以數(shù)組形式返回這個(gè)區(qū)間。要求題目必須在輸入數(shù)組和目標(biāo)值返回想法我們需要分別找出最左邊的這個(gè)元素的位置和最右邊的這個(gè)元素的位置。由于對(duì)于時(shí)間的要求，我們?cè)谶M(jìn)行查找的時(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].
題目的意思是，輸入一個(gè)升序排列的整數(shù)數(shù)組和一個(gè)目標(biāo)值。我們要找出這個(gè)目標(biāo)數(shù)字在數(shù)組中的存在區(qū)間，并以數(shù)組形式返回這個(gè)區(qū)間。如果這個(gè)數(shù)字不存在于數(shù)組之中，則返回｛－1.－1｝。要求題目必須在O(logn)


For example,
輸入數(shù)組[5, 7, 7, 8, 8, 10]和目標(biāo)值8,
返回[3, 4].
想法

我們需要分別找出最左邊的這個(gè)元素的位置、和最右邊的這個(gè)元素的位置。

由于對(duì)于時(shí)間的要求，我們?cè)谶M(jìn)行查找的時(shí)候要采取二分查找。

需要注意的是，對(duì)于尋找左邊界的時(shí)候，如果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;
    }

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/68489.html

相關(guān)文章

  • leetcode34 search for a range

    摘要：題目要求即在一個(gè)有序排列的數(shù)組中，找到目標(biāo)值所在的起始下標(biāo)和結(jié)束下標(biāo)。這樣一定可以找到目標(biāo)值的初始下標(biāo)同理，結(jié)合情況和情況，當(dāng)中間值大于目標(biāo)值，則將右指針左移至中間，否則將左指針右移至中間，這樣一定可以找到目標(biāo)值的結(jié)束下標(biāo)。 題目要求 Given an array of integers sorted in ascending order, find the starting and ...

    2shou 評(píng)論0 收藏0

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

    摘要：二分搜索復(fù)雜度時(shí)間空間思路其實(shí)就是執(zhí)行兩次二分搜索，一次專(zhuān)門(mén)找左邊邊界，一次找右邊邊界。如果找右邊邊界，則要判斷右邊一位的數(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 評(píng)論0 收藏0

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

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

    leo108 評(píng)論0 收藏0

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

    摘要：首先，建立二元結(jié)果數(shù)組，起點(diǎn)，終點(diǎn)。二分法求左邊界當(dāng)中點(diǎn)小于，移向中點(diǎn)，否則移向中點(diǎn)先判斷起點(diǎn)，再判斷終點(diǎn)是否等于，如果是，賦值給。 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 評(píng)論0 收藏0

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

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

    haobowd 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<