leetcode34--在排序数组中查找元素的第一个和最后一个位置

原题

给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值,返回 [-1, -1]

示例1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

示例2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

解法

思想

二分查找,找到一个目标值时向两边继续查找最初和最末出现的地方。

代码

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] pos = new int[2];
        int start = 0;
        int end = nums.length - 1;
        if(end == -1) return new int[]{-1,-1};
        int mid = start + (end-start)/2;
        while(nums[mid]!=target &&start<=end){
            mid = start + (end-start)/2;
            if(nums[mid]<target) start = mid + 1;
            else if(nums[mid] > target) end = mid -1;
        }
        if(nums[mid]!=target) return new int[]{-1,-1};
        int mid_cache = mid;
        int end_cache = end;
        end = mid;
        while(start<end){
            mid = start + (end-start)/2;
            if(nums[mid] == target) end = mid;
            else if(nums[mid] < target) start = mid+1;
        }
        pos[0] = start;
        start = mid_cache;
        end = end_cache;
        while(start<end){
            mid = start + (end-start+1)/2;
            if(nums[mid] == target) start = mid;
            else if(nums[mid] > target) end = mid-1;
        }
        pos[1] = end;
        return pos;       
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode34-%e5%9c%a8%e6%8e%92%e5%ba%8f%e6%95%b0%e7%bb%84%e4%b8%ad%e6%9f%a5%e6%89%be%e5%85%83%e7%b4%a0%e7%9a%84%e7%ac%ac%e4%b8%80%e4%b8%aa%e5%92%8c%e6%9c%80%e5%90%8e%e4%b8%80%e4%b8%aa%e4%bd%8d/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年1月3日
下一篇 2020年1月4日

相关推荐

  • leetcode706-设计哈希映射

    原题 不使用任何内建的哈希表库设计一个哈希映射 具体地说,你的设计应该包含以下的功能 put(key, value):向哈希映射中插入(键,值)的数值对。如果键对应的值已经存在,更…

    算法 2019年12月18日
    0120
  • leetcode54-螺旋矩阵

    原题 给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。 示例 1: 输入: [ [ 1, 2, 3 ], [ 4, 5, 6…

    算法 2019年11月15日
    0100
  • 蓝桥杯试题-小数第n位

    原题 资源限制 时间限制:1.0s 内存限制:256.0MB 问题描述   我们知道,整数做除法时,有时得到有限小数,有时得到无限循环小数。  如果我们把有限小数的末尾加上无限多个…

    算法 2020年2月29日
    080
  • leetcode3-无重复字符的最长子串

    原题 给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 示例1: 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长…

    2019年12月26日
    0100
  • leetcode199-二叉树的右视图

    原题 给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。 示例: 输入: [1,2,3,null,5,null,4] 输出:&nb…

    算法 2020年4月22日
    0110
  • leetcode131-分割回文串

    原题 给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。 返回 s 所有可能的分割方案。 示例: 输入: "aab" 输出: [ ["aa","b"], …

    算法 2020年5月22日
    0100
  • 剑指offer47-礼物的最大价值

    原题(来源Leetcode) 在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一…

    算法 2020年6月12日
    090
  • leetcode328-奇偶链表

    原题 给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。 请尝试使用原地算法完成。你的算法的空…

    算法 2019年12月16日
    0130
  • leetcode200-岛屿数量

    原题 给定一个由 '1'(陆地)和 '0'(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水…

    算法 2019年11月24日
    0150
  • leetcode837-新21点

    原题 爱丽丝参与一个大致基于纸牌游戏 “21点” 规则的游戏,描述如下: 爱丽丝以 0 分开始,并在她的得分少于 K 分时抽取数字。 抽取时,她从 [1, W] 的范围中随机获得一…

    算法 2020年6月3日
    0110

发表回复

登录后才能评论