[LeetCode] Find First and Last Position of Element

Loong_T 发布于2019-08-19 11:08 / 1330人阅读

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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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