LeetCode做题笔记————34顺序队列中找元素区间

唠唠

这题要求给出了条件：队列升序，且给出了时间复杂度的要求：O(log n)，很显然是需要我们使用二分查找的思想求解，但是二分查找我们通常进行的是点查询，而该题乍一看是需要我们进行区间查询。

但实际上区间查询的本质是需要我们找到区间的两个端点。即：

最后一个比target小的数字
第一个比target大的数字

这就需要我们对原本的二分查找进行改写，使得它能找到与target有关的相邻数字，而不是target。

题面

现在我们有一个非严格上升的升序序列nums，给出一个目标值target，请给出指定目标值在序列中的第一个和最后一个位置。如果不存在则输出[-1, -1]。

要求时间复杂度为O(n)

分析

首先我们可以通过题目给出的限制条件可以知道本体需要我们使用二分查找来写。因此与本体结合的第一个思路就诞生了：

可以使用二分查找到一个targt，然后从该target出发，分别向左右扩散，从而找到边界

这个方法看起来很行但实际上，如果我们的数组全是target的话，该算法的时间复杂度将退化为O(n)

因此，我们可以思考出，需要用二分查找，来找到目标序列的出生位置和死亡位置，即：

最后一个比target小的数字
第一个比target大的数字

我们先来看看普通的二分查找是怎么写的：

int findTarget(vector<int> &nums, int target)
{
    int n = nums.size();
    int l = 0, r = n - 1;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if(nums[mid] == target) {
            return mid;
        }
        else if (nums[mid] > target)
        {
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    return -1;
}

然后我们先来思考，如何找到最后一个小于target的值的所在位置。

首先当遇到nums[mid] == target时显然不能直接返回
遇到nums[mid] == target时，我们应该继续往左边的区间寻找
当查询区间向左进行缩小时，mid很可能是我们要找的答案

综上，对于寻找区间的方法我们就能改写为如下形式：

int findTarget(vector<int> &nums, int target)
{
    int n = nums.size();
    int l = 0, r = n - 1;
    int ans = n;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        else if (nums[mid] >= target)
        {
            r = mid - 1;
            ans = mid
        }
        else
        {
            l = mid + 1;
        }
    }
    return ans;
}

同理我们思考区间右侧的元素如何寻找：

同样遇到nums[mid] == target时不能直接返回
当nums[mid] == target时，我们应该往右边的区间寻找
当查询区间向右进行缩小时，mid很可能时我们要寻找的答案

int findTarget(vector<int> &nums, int target)
{
    int n = nums.size();
    int l = 0, r = n - 1;
    int ans = n;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        else if (nums[mid] >= target)
        {
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
            ans = mid;
        }
    }
    return ans;
}

最后为了提升代码的复用性，我们需要将两个代码进程整合，需要注意的是为了整合方便，我们将第二个方法中的ans = mid，移动到上面一个if中使其与第一个方法的形式相似，并增加一个参数来控制寻找左界还是右界。

int findTarget(vector<int> &nums, int target, int lower)
{
    int n = nums.size();
    int l = 0, r = n - 1;
    int ans = n;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (nums[mid] > target || (lower && nums[mid] >= target))
        {
            r = mid - 1;
            ans = mid;
        }
        else
        {
            l = mid + 1;
        }
    }
    return ans;
}

代码

int findTarget(vector<int> &nums, int target, int lower)
{
    // 0 6 6 6 6 6 7
    int n = nums.size();
    int l = 0, r = n - 1;
    int ans = n;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (nums[mid] > target || (lower && nums[mid] >= target))
        {
            r = mid - 1;
            ans = mid;
        }
        else
        {
            l = mid + 1;
        }
    }
    return ans;
}

vector<int> searchRange(vector<int> &nums, int target)
{

    int leftMark = findTarget(nums, target, true);
    int rightMark = findTarget(nums, target, false) - 1;
    if (leftMark <= rightMark && rightMark < nums.size() && nums[leftMark] == target && nums[rightMark] == target)
    {
        return vector<int>{leftMark, rightMark};
    }
    return vector<int>{-1, -1};
}