34. 在排序数组中查找元素的第一个和最后一个位置(二分查找)

这篇具有很好参考价值的文章主要介绍了34. 在排序数组中查找元素的第一个和最后一个位置(二分查找)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

二分查找到目标值然后左右找到坐标

问题在于:找左右坐标的时候时间复杂度不是O(logN)

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] ans = {-1, -1};
        if (nums.length == 0) return ans;
        int l = 0, r = nums.length;
        while (l < r) {
            int m = (l + r) / 2;
            if (nums[m] == target) {
                ans[0] = m; ans[1] = m;
                int tempm = m;
                while (m > 0 && nums[m - 1] == target) {
                    ans[0] = --m;
                }
                while (tempm < nums.length - 1 && nums[tempm + 1] == target) {
                    ans[1] = ++tempm;
                }
                break;
            } else if (nums[m] < target) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        return ans;
    }
}

之前提到过二分查找不仅可找到相等的数值,更关键的是它可以将数组分为截然不同的两种情况,因此我们可以借助这个性质找到第一个大于等于target的值(左下标)第一个大于target的值(右下标需要-1)(两次二分查找)

找到第一个>=x的值和找到第一个>x的值见:

2258. 逃离火灾(附:二分查找的理解)文章来源地址https://www.toymoban.com/news/detail-813929.html

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] ans = {-1, -1};
        if (nums.length == 0) return ans;
        int lIndex = func(0, nums.length, nums, target);
        int rIndex = func(0, nums.length, nums, target + 1) - 1;
        if (lIndex <= rIndex) ans = new int[] {lIndex, rIndex};
        return ans;
    }
    public int func(int l, int r, int[] nums, int x) {
        int res = -1;
        // 找到第一个大于等于x的下标(left)
        // 大于等于target正常使用
        // 大于target相当于大于(target + 1)
        while (l < r) {
            int m = (l + r) / 2;
            if (nums[m] < x) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        res = l;
        return res;
    }
}

到了这里,关于34. 在排序数组中查找元素的第一个和最后一个位置(二分查找)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode 34 在排序数组中查找元素的第一个和最后一个位置

    在排序数组中查找元素的第一个和最后一个位置 给你一个按照非递减顺序排列的整数数组 nums ,和一个目标值 target 。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target ,返回 [-1, -1] 。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此

    2024年02月02日
    浏览(46)
  • 二分查找实例1(在排序数组中查找元素的第一个和最后一个位置)

    给你一个按照非递减顺序排列的整数数组  nums ,和一个目标值  target 。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值  target ,返回  [-1, -1] 。 你必须设计并实现时间复杂度为  O(log n)  的算法解决此问题。 示例 1: 示例 2: 示例 3: 提示

    2024年02月09日
    浏览(46)
  • 84.在排序数组中查找元素的第一个和最后一个位置(力扣)

    目录 问题描述 代码解决以及思想  知识点  初始化左边界 left 为数组的起始位置(0),右边界 right 为数组的结束位置( nums.size() - 1 )。 进入一个循环,只要左边界 left 不大于右边界 right ,就执行以下操作: a. 计算中间位置 middle ,这是为了进行二分查找,以避免整数溢

    2024年02月06日
    浏览(44)
  • 在排序数组中查找元素的第一个和最后一个位置(Java详解)

    给你一个按照 非递减 顺序排列的整数数组  nums ,和一个目标值  target 。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值  target ,返回  [-1, -1] 。 你必须设计并实现时间复杂度为   O(log n)  的算法解决此问题。 示例: 输入:nums = [5,7,7,8,8

    2024年02月03日
    浏览(54)
  • 【算法Hot100系列】在排序数组中查找元素的第一个和最后一个位置

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月02日
    浏览(49)
  • 【LeetCode】每日一题&&两数之和&&寻找正序数组的中位数&&找出字符串中第一个匹配项的下标&&在排序数组中查找元素的第一个和最后一个位置

    ========================================================================= 主页点击直达: 个人主页 我的小仓库: 代码仓库 C语言偷着笑: C语言专栏 数据结构挨打小记: 初阶数据结构专栏 Linux被操作记: Linux专栏 LeetCode刷题掉发记: LeetCode刷题 算法: 算法专栏  C++头疼记: C++专栏 计算机

    2024年02月08日
    浏览(55)
  • 「优选算法刷题」:在排序数组中查找元素的第一个和最后个位置

    给你一个按照非递减顺序排列的整数数组  nums ,和一个目标值  target 。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值  target ,返回  [-1, -1] 。 你必须设计并实现时间复杂度为  O(log n)  的算法解决此问题。 示例 1: 示例 2: 示例 3: 二分

    2024年01月22日
    浏览(43)
  • 【leetcode题解C++】34.在排序数值中查找第一个和最后一个位置

    给你一个按照非递减顺序排列的整数数组  nums ,和一个目标值  target 。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值  target ,返回  [-1, -1] 。 你必须设计并实现时间复杂度为  O(log n)  的算法解决此问题。 示例 1: 示例 2: 示例 3: 思路

    2024年01月16日
    浏览(40)
  • 代码随想录额外题目| 数组03 ●34排序数组查首尾位置 ●922按奇偶排序数组II●35搜索插入位置

    #34排序数组查首尾位置 medium,我写的:1 暴力 我写的,做了个类似二分搜索的方法: 随想录:从两头都做类似二分搜索 #922 按奇偶排序数组II 我的解法,有点蠢: inplace解法: 把odd idx放的偶数,给换到even idx放的奇数 注意j是从1开始,而且每轮i,j都是继续增加不回去 空间表

    2024年02月15日
    浏览(42)
  • 【LeetCode】2619. 数组原型对象的最后一个元素

    请你编写一段代码实现一个数组方法,使任何数组都可以调用 array.last() 方法,这个方法将返回数组最后一个元素。如果数组中没有元素,则返回 -1 。 你可以假设数组是 JSON.parse 的输出结果。 示例 1 : 输入: nums = [null, {}, 3] 输出: 3 解释:调用 nums.last() 后返回最后一个元

    2024年01月21日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包