LeetCode

LeetCode-34-find-positions-of-elements

二分查找。

  • 描述

    在一个有序的数组中找到指定元素的起始和结束位置，如下：

    1
    2
    Input: nums = [5,7,7,8,8,10], target = 8
    Output: [3,4]

    如果没有找到target，返回[-1, -1]。

  • 思路

    分两步，首先用二分查找法找到数组中的一个target，然后分别从这个target开始先前和向后移动，找到其开始和结束的位置。实现如下，时间复杂度O(m*logN)，m为target元素个数：

  • 实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    class Solution {
    public:
        // 二分查找
        vector<int> searchRange(vector<int>& nums, int target) {
            if(nums.size()==0) return vector<int>{-1,-1};

            int head = 0;
            int tail = nums.size()-1;
            while(head<=tail){
                int m = (tail+head)/2;
                if(nums[m] == target) {
                    return mySearch(m, nums);
                }
                else if(nums[m] < target)
                    head = m + 1;
                else
                    tail = m - 1;
            }
            // 当没有找到target
            return vector<int> {-1, -1};
        }   
    private:
        // 搜索起始和结束位置
        vector<int> mySearch(int m, vector<int>& nums){
            int mUp = m;
            int mDown = m;
            // 向后搜索
            while(mUp+1<nums.size() && nums[mUp] == nums[mUp+1]) 
                mUp++;
            // 向前搜索
            while(mDown-1>=0 && nums[mDown] == nums[mDown-1]) 
                mDown--;
            return vector<int>{mDown, mUp};
        }   
    };