[LeetCode] Find First and Last Position of Element

Loong_T 發布于2019-08-19 11:08 / 1343人閱讀

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云服務器 share-and-find Element LeetCode LeetCode_String

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/77059.html

[LintCode/LeetCode] Jump Game I & II

摘要：建立動規數組，表示從起點處到達該點的可能性。循環結束后，數組對所有點作為終點的可能性都進行了賦值。和的不同在于找到最少的步數。此時的一定是滿足條件的最小的，所以一定是最優解。 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 通配符匹配

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

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

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

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

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

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

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

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