LeetCode_34_在排序数组中查找元素的第一个和最后一个位置

❗️剑指Offer_53-1_在排序数组中查找数字1

题目描述：

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

示例：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

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

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

提示：
1. 0 <= nums.length <= 10^5
2. -10^9 <= nums[i] <= 10^9
3. nums 是一个非递减数组
4. -10^9 <= target <= 10^9

解法1：二分查找

//这道题可以看作是自己实现C++里的lower_bound和upper_bound函数
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {

        if (nums.empty()) return vector<int> {-1,-1};

        //二分查找尤其要注意边界值，尽量使用左闭右闭的写法
        int lower = lower_bound(nums,target);
        int upper = upper_bound(nums,target) - 1;  //注意这里需要减1

        //[5,7,7,8,8,10] 6
        //[2,2] 3
        if (lower == nums.size() || nums[lower] != target) {
            return vector<int> {-1,-1};
        }

        return vector<int> {lower,upper};
    }

    //查找元素的第一个位置
    int lower_bound(vector<int> &nums,int target) {

        int l = 0,r = nums.size() - 1,mid;

        while (l <= r) {

            mid = (l + r) / 2;

            if (nums[mid] >= target) r = mid - 1;
            else l = mid + 1;
        }

        return l;
    }

    //查找元素的最后一个位置
    int upper_bound(vector<int> &nums,int target) {

        int l = 0,r = nums.size() - 1,mid;

        while (l <= r) {

            mid = (l + r) / 2;

            if (nums[mid] > target) r = mid - 1;
            else l = mid + 1;
        }

        return l;
    }
};

//剑指Offer_53-1_在排序数组中查找数字1
//解法2：哈希表
class Solution {
public:
    int search(vector<int>& nums, int target) {

        unordered_map<int,int> map;

        for (auto num : nums) ++map[num];

        for (auto a : map) {

            if (a.first == target) return a.second;
        }

        return 0;
    }
};