• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

9 找到目标出现的区间范围(Search for a range)

开发技术 开发技术 4小时前 1次浏览

目录
  • 1 题目
  • 2 描述
  • 3 思路
    • 3.1 图解
    • 3.2 时间复杂度
    • 3.3 空间复杂度
  • 4 源码

1 题目

  找到目标出现的区间范围(Search for a range)

lintcode:题号——61,难度——medium

2 描述

  给定一个包含 n 个整数的排序数组,找出给定目标值 target 的起始和结束位置。如果目标值不在数组中,则返回[-1, -1]。

  样例1:

输入:数组 = [],target = 9
输出:[-1,-1]
解释:

9不在数组中。

  样例2:

输入:数组 = [5, 7, 7, 8, 8, 10],target = 8
输出:[3,4]
解释:

数组的[3,4]子区间值都为8。

3 思路

  在已排序的数组中,寻找目标出现的范围,找到目标出现的初始和最后位置[1],它们中间的区间即是目标区间,二分搜索套模版[2],跑两次就能得到结果。

  1. 找到目标出现的初始位置;
  2. 找到目标出现的最后位置;
  3. 得到目标区间。

3.1 图解

输入:数组 = [5, 6, 7, 9, 9, 9, 10, 12],target = 9
输出:[3,5]
解释:

数组的[3,5]子区间值都为8。

graph TD
X[原数组 ‘5, 6, 7, 9, 9, 9, 10, 12’] — 寻找初始位置 –> A
A[‘5, 6, 7, 9, 9, 9, 10, 12′] — 中间位置元素’9′,等于目标元素’9′ –>A1
A1 — 抛掉 –> B[抛掉’5’]
A1[‘5, 6, 7, 9′] — 中间位置元素’6′,小于目标元素’9’ –> A2
A — end = mid –> C[/抛掉’9, 9, 10, 12’/]
A2[‘6, 7, 9′] — 中间位置元素’7′,小于目标元素’9’ –> A3
A3[‘7, 9’] — 先比头,再比尾部 –> A4[元素9初始下标3]

X — 寻找最后位置 –> D[‘5, 6, 7, 9, 9, 9, 10, 12’]
D — 略,同左边 –> D1[元素9最后位置5]

A4 –> Y[区间3,5]
D1 –> Y

3.2 时间复杂度

  在n规模的问题上使用两次二分法,时间复杂度为O(2 * log n),依然是O(log n)。

3.3 空间复杂度

  算法的空间复杂度为O(1)。

4 源码

  C++版本:

/**
* @param A: 已排序数组
* @param target: 目标值
* @return: 目标出现的区间范围
*/
vector<int> searchRange(vector<int> &A, int target) {
    // write your code here
    vector<int> result;
    if (A.empty())
    {
        result.push_back(-1);
        result.push_back(-1);
        return result;
    }

    int startPos = -1;
    int endPos = -1;
    startPos = findFirstPos(A, target);
    endPos = findLastPos(A, target);
    result.push_back(startPos);
    result.push_back(endPos);

    return result;
}

int findFirstPos(vector<int> & A, int target)
{
    int start = 0;
    int end = A.size() - 1;
    int mid = 0;
    while (start + 1 < end)
    {
        mid = start + (end - start) / 2;
        if (A.at(mid) >= target)
        {
            end = mid;
        }
        if (A.at(mid) < target)
        {
            start = mid;
        }
    }

    if (A.at(start) == target)
    {
        return start;
    }
    if (A.at(end) == target)
    {
        return end;
    }

    return -1;
}

int findLastPos(vector<int> & A, int target)
{
    int start = 0;
    int end = A.size() - 1;
    int mid = 0;
    while (start + 1 < end)
    {
        mid = start + (end - start) / 2;
        if (A.at(mid) <= target)
        {
            start = mid;
        }
        if (A.at(mid) > target)
        {
            end = mid;
        }
    }

    if (A.at(end) == target)
    {
        return end;
    }
    if (A.at(start) == target)
    {
        return start;
    }

    return -1;
}

  1. 寻找目标出现的初始or最后位置:https://blog.csdn.net/SeeDoubleU/article/details/118346371 ↩︎

  2. 经典二分搜索:https://blog.csdn.net/SeeDoubleU/article/details/118271548 ↩︎


程序员灯塔
转载请注明原文链接:9 找到目标出现的区间范围(Search for a range)
喜欢 (0)