剑指53：在排序数组中查找数字

传送门

nowcoder
leetcode

题目描述

给定一个长度为 n 的非降序数组和一个非负数整数 k ，统计 k 在数组中出现的次数。
数据范围：0 <= n <= 1000, 0 <= k <= 100，数组中每个元素的值满足 0 <= val <= 100
要求：时间复杂度 O(logn)，空间复杂度 O(1)

C++ 代码 - nowcoder

/*
    哈希表
    
    时间复杂度：O(logn)
    空间复杂度：O(n)
*/
class Solution {
public:
    int GetNumberOfK(vector<int>& nums, int k) {
        if (nums.size() <= 0) return 0;

        unordered_map<int, int> hash;
        for (int i = 0; i < nums.size(); i ++) {
            hash[nums[i]] ++;
        }

        return hash[k] > 0 ? hash[k] : 0;
    }
};


/*
	两次二分查找
    第一次二分：
        查找第一个位置大于等于 target。若该位置的值不等于 target，则返回 [-1, -1]。
    第二次二分：
        查找第一个位置小于等于 target。注意需要特判边界。

    时间复杂度：O(logn)
*/
class Solution {
public:
    int GetNumberOfK(vector<int>& nums, int target) {
        if (nums.empty()) return 0;

        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        if (nums[r] != target) return 0;

        int leftIndex = r;
        l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (nums[mid] <= target) l = mid;
            else r = mid - 1;
        }
        int rightIndex = r;

        return rightIndex - leftIndex + 1;
    }
};

C++ 代码 - leetcode

/*
	二分搜索找到左右边界的索引，然后判断重复出现的次数。
	
	时间复杂度：O(logn)
*/
class Solution {
public:
    int countTarget(vector<int>& nums, int target) {
        int left_index = left_bound(nums, target);
        if (left_index == -1) return 0;
        int right_index = right_bound(nums, target);

        // 根据左右边界，推导出元素出现的次数
        return right_index - left_index + 1;
    }

    int left_bound(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        // 搜索区间为 [left, right]
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                // 搜索区间变为 [mid + 1, right]
                left = mid + 1;
            } else if (nums[mid] > target) {
                // 搜索区间变为 [left, mid - 1]
                right = mid - 1;
            } else if (nums[mid] == target) {
                // 收缩右侧边界
                right = mid - 1;
            }
        }
        // 检查出界情况
        if (left >= nums.size() || nums[left] != target) {
            return -1;
        }

        return left;
    }

    int right_bound(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] == target) {
                // 这里改成收缩左侧边界
                left = mid + 1;
            }
        }
        // 这里改为检查 right 越界的情况
        if (right < 0 || nums[right] != target) {
            return -1;
        }

        return right;
    }
};