1. 代码段小站首页
  2. 算法

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

彭晨涛 • • 算法 • 阅读 14

原题

给定一个按照升序排列的整数数组 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)
彭晨涛彭晨涛管理者
0 0
上一篇 2020年1月3日 15:59
下一篇 2020年1月4日 20:08

相关推荐

  • 'leetcode50-Pow(x,n)'

    原题 实现 pow(x, n) ，即计算 x 的 n 次幂函数。 示例1： 输入： 2.00000, 10 输出： 1024.00000 示例2： 输入： 2.10000, 3 输...

    彭晨涛 彭晨涛
    算法 2020年1月5日
    0160

  • leetcode205-同构字符串

    原题 给定两个字符串 s 和 t，判断它们是否是同构的。 如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。 所有出现的字符都必须用另一个字符替换，同时保留字符的顺...

    彭晨涛 彭晨涛
    算法 2019年12月21日
    0190

  • leetcode837-新21点

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

    彭晨涛 彭晨涛
    算法 2020年6月3日
    0100

  • leetcode95-不同的二叉搜索树II

    原题 给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？ 示例: 输入: 3 输出: [   [1,null,3,2],  &n...

    彭晨涛 彭晨涛
    算法 2020年1月22日
    0700

  • leetcode409-最长回文串

    原题 给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。 在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。 注意:假设字符串的长...

    彭晨涛 彭晨涛
    算法 2020年3月19日
    0530

  • leetcode108-将有序数组转换为二叉搜索树

    原题 将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。 示例: 给定有序数...

    彭晨涛 彭晨涛
    算法 2020年1月18日
    080

  • leetcode820-单词的压缩编码

    原题 给定一个单词列表，我们将这个列表编码成一个索引字符串 S 与一个索引列表 A。 例如，如果这个列表是 ["time", "me", "bell"]，我们就可以将其表示为 S ...

    彭晨涛 彭晨涛
    算法 2020年3月28日
    080

  • leetcode82-删除排序链表中的重复元素II

    原题 给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。 示例 1: 输入: 1->2->3->3->4->4->5 输出: 1->2->5 示...

    彭晨涛 彭晨涛
    算法 2020年5月31日
    0210

  • leetcode374-猜数字大小

    原题 我们正在玩一个猜数字游戏。 游戏规则如下：我从 1 到 n 选择一个数字。 你需要猜我选择了哪个数字。每次你猜错了，我会告诉你这个数字是大了还是小了。你调用一个预先定义好的接...

    彭晨涛 彭晨涛
    算法 2019年12月31日
    0310

  • leetcode341-扁平化嵌套列表迭代器

    原题 给定一个嵌套的整型列表。设计一个迭代器，使其能够遍历这个整型列表中的所有整数。 列表中的项或者为一个整数，或者是另一个列表。 示例1： 输入: [[1,1],2,[1,1]]...

    彭晨涛 彭晨涛
    算法 2020年1月27日
    050

发表回复

登录后才能评论