前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode题目34:在排序数组中查找元素的第一个和最后一个位置

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

作者头像
二环宇少
发布2020-08-13 15:46:20
3.1K0
发布2020-08-13 15:46:20
举报
文章被收录于专栏:互联网西门二少

原题描述

+

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

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

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

示例 1

代码语言:javascript
复制
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

示例 2

代码语言:javascript
复制
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

原题链接:https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array

思路解析

+

毫无疑问,时间复杂度O(log n)和升序数组,提示了我们使用二分查找的解法。

普通的二分查找在找到target后立即返回,所以我们需要做变式,情况分为以下两种。

寻找左边界

还是得举个例子。假设nums=[5, 7, 7, 8, 8, 10],target=7,那么应用一次二分查找得到:

显然不能立即返回,应该让mid作为新的边界,再做一次二分查找,mid才能指向预期结果。

那么问题来了,我们只知道当mid指向了target应该仍然继续二分查找下去,但却不知道应该经过多少次查找为止。

当nums[mid]大于或等于target时(等于的情况也必须要挪动,因为要尽可能的逼近边界),我们一定会不断让higher向左挪动,使它将不断靠近lower。只有nums[mid]小于target时,我们才会向右挪动lower。此时由于我们已经知道nums[mid]不等于target,所以lower要挪动到mid+1的位置。

那么这种情况下,当lower和higher相撞,该点一定是左边界。因为lower的左边不是target,而higher也一直在尽可能的往左挪动。

寻找右边界

与上面过程相反,我们尽可能向右挪动lower,让其与higher相撞即可。即当nums[mid]小于或等于target时,要挪动lower。但如果复用上面的逻辑,每次挪动时令lower=mid+1,那么最终lower一定会与higher相撞于最后一个target的后一个位置。此时lower-1才是所求。

这样调用两次二分查找逻辑,就可以完成题目。实现时,为了能重用二分查找逻辑,可以增加一个参数来控制寻找左边界还是右边界。

复杂度分析

+

  • 时间复杂度:O(log n)
  • 空间复杂度:O(1)

C++参考代码

+

代码语言:javascript
复制
class Solution {
public:

    int find_boudary(vector<int>& nums, int target, bool left) {
        int lower = 0;
        int upper = nums.size();
        while (lower < upper) {
            int mid = (lower + upper) / 2;
            if ((nums[mid] > target) || (left && nums[mid] == target)) {
                upper = mid;
            } else {
                lower = mid + 1;
            }
        }

        return lower;
    }

    vector<int> searchRange(vector<int>& nums, int target) {
        int left_most = find_boudary(nums, target, true);

        if (left_most == nums.size() || nums[left_most] != target) {
            return {-1, -1};
        }

        int right_most = find_boudary(nums, target, false) - 1;
        return {left_most, right_most};
    }
};
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-07-31,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 互联网西门二少 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档