[LeetCode] Find First and Last Position of Element

Loong_T 發(fā)布于2019-08-19 11:08 / 1418人閱讀

Problem

Given an array of integers nums 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].

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Solution

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] res = {-1, -1};
        if (nums == null || nums.length == 0) return res;
        int start = 0, end = nums.length-1;
        while (nums[start] < nums[end]) {                   //don"t be equal
            int mid = start + (end-start)/2;
            if (nums[mid] < target) {
                start = mid+1;
            } else if (nums[mid] > target) {
                end = mid-1;
            } else {                                        //once nums[mid] == target:
                if (nums[start] != nums[mid]) start++;      //move start to lower bound (first position)
                else end--;                                 //move end to higher bound (last position)
            }
        }
        
        if (nums[start] == target && nums[end] == target) {
            res[0] = start;
            res[1] = end;
        }
        return res;
    }
}

GPU云服務(wù)器云服務(wù)器 share-and-find Element LeetCode LeetCode_String

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

轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/77059.html

相關(guān)文章

[LintCode/LeetCode] Jump Game I & II

摘要：建立動規(guī)數(shù)組，表示從起點(diǎn)處到達(dá)該點(diǎn)的可能性。循環(huán)結(jié)束后，數(shù)組對所有點(diǎn)作為終點(diǎn)的可能性都進(jìn)行了賦值。和的不同在于找到最少的步數(shù)。此時(shí)的一定是滿足條件的最小的，所以一定是最優(yōu)解。 Jump Game Problem Given an array of non-negative integers, you are initially positioned at the first index...

rose 2019-08-14 15:27 評論0 收藏0
Leetcode 44 Wildcard Matching 通配符匹配

摘要：難度題目給出一個(gè)字符串和一個(gè)要求我們給出這個(gè)字符串是否匹配這個(gè)其中通配符跟我們平常見到的一樣是和代表任意單個(gè)字符代表一個(gè)或多個(gè)字符這個(gè)題跟簡單正則匹配比較類似可以跟這里面第二個(gè)解法一樣采取類似的動態(tài)規(guī)劃解法在里取中間某個(gè)確定的字符串序列將字 Implement wildcard pattern matching with support for ? and *. ? Matches ...

SimonMa 2019-08-14 17:16 評論0 收藏0
前端 | 每天一個(gè) LeetCode

摘要：在線網(wǎng)站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。這篇文章記錄我練習(xí)的 LeetCode 題目，語言 JavaScript。在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0
LRU & LFU Cache

摘要：首先要做到是，能想到的數(shù)據(jù)結(jié)構(gòu)只有兩三種，一個(gè)是，一個(gè)是，是，還有一個(gè)，是。不太可能，因?yàn)殚L度要而且不可變，題目也沒說長度固定?？梢宰龅胶投际?。因?yàn)檫€有函數(shù)，要可以，所以還需要一個(gè)數(shù)據(jù)結(jié)構(gòu)來記錄順序，自然想到。 LRU Cache 題目鏈接：https://leetcode.com/problems... 這個(gè)題要求O(1)的復(fù)雜度。首先要做到get(key)是O(1)，能想到的數(shù)據(jù)結(jié)...

wenshi11019 2019-08-14 17:20 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經(jīng)到題，所以后面會調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時(shí)，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。一目錄不折騰的前端，和咸魚有什么區(qū)別...

tain335 2019-08-26 10:28 評論0 收藏0