写点什么

leetcode 34. Find First and Last Position of Element in Sorted Array 在排序数组中查找元素的第一个和最后一个位置 (中等)

作者:okokabcd
  • 2022 年 5 月 26 日
  • 本文字数:989 字

    阅读完需:约 3 分钟

leetcode 34. Find First and Last Position of Element in Sorted Array 在排序数组中查找元素的第一个和最后一个位置(中等)

一、题目大意

标签: 查找


https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array


给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target,返回 [-1, -1]。


进阶:


  • 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗?


示例 1:


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


示例 2:


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


示例 3:


输入:nums = [], target = 0 输出:[-1,-1]


提示:


  • 0 <= nums.length <= 105

  • -109 <= nums[i] <= 109

  • nums 是一个非递减数组

  • -109 <= target <= 109

二、解题思路

给定一个增序的整数数组和一个值,查找该值第一次和最后一次出现的位置。使用二分查找找左右区间。lower_bound 返回的是开始的第一个满足条件的位置,upper_bound 返回的是第一个不满足条件的位置。所以当两个返回值相等的时候表示没有找到,找到了需要返回的是{left, right - 1}

三、解题方法

3.1 Java 实现

public class Solution2 {    public int[] searchRange(int[] nums, int target) {        int left = lower_bound(nums, target);        int right = upper_bound(nums, target);        if (left == right) {            return new int[]{-1, -1};        }        return new int[]{left, right - 1};    }
private int lower_bound(int[] nums, int target) { int left = 0; int right = nums.length; int mid; while (left < right) { mid = left + (right - left) / 2; if (nums[mid] >= target) { right = mid; } else { left = mid + 1; } } return left; }
private int upper_bound(int[] nums, int target) { int left = 0; int right = nums.length; int mid; while (left < right) { mid = left + (right - left) / 2; if (nums[mid] > target) { right = mid; } else { left = mid + 1; } } return left; }}
复制代码

四、总结小记

  • 2022/5/26 二分查找 l 时间复杂度 O(logn)

发布于: 刚刚阅读数: 5
用户头像

okokabcd

关注

还未添加个人签名 2019.11.15 加入

还未添加个人简介

评论

发布
暂无评论
leetcode 34. Find First and Last Position of Element in Sorted Array 在排序数组中查找元素的第一个和最后一个位置(中等)_LeetCode_okokabcd_InfoQ写作社区