c++中如何统计有序数组中元素出现次数_c++有序数组元素出现次数统计-C++-PHP中文网

使用二分查找通过lower_bound和upper_bound确定左右边界，其差值即为目标元素出现次数，时间复杂度O(log n)，代码简洁高效。

c++中如何统计有序数组中元素出现次数_c++有序数组元素出现次数统计

在C++中统计有序数组中某个元素的出现次数，可以利用数组的有序特性，使用二分查找来高效定位目标元素的左右边界，从而计算出其出现次数。这种方法时间复杂度为 O(log n)，远优于暴力遍历的 O(n)。

1. 使用 lower_bound 和 upper_bound

C++标准库提供了 std::lower_bound 和 std::upper_bound，非常适合处理有序数组：

lower_bound 返回第一个不小于目标值的迭代器
upper_bound 返回第一个大于目标值的迭代器
两者之差即为目标元素的出现次数

示例代码：

#include 
#include 
#include 
int countOccurrences(const std::vector& arr, int target) {
auto left = std::lower_bound(arr.begin(), arr.end(), target);
auto right = std::upper_bound(arr.begin(), arr.end(), target);
return right - left;
}
int main() {
std::vector arr = {1, 2, 2, 2, 3, 4, 5};
int target = 2;
std::cout << target << " 出现了 " << countOccurrences(arr, target) << " 次\n";
return 0;
}

2. 手动实现二分查找

如果不使用STL函数，也可以手动实现二分查找来找到左右边界：

立即学习“C++免费学习笔记（深入）”；

查找左边界：

Adrenaline

软件调试助手，识别和修复代码中错误

下载

int findLeftBound(const std::vector& arr, int target) {
    int left = 0, right = arr.size();
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

查找右边界：

int findRightBound(const std::vector& arr, int target) {
    int left = 0, right = arr.size();
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

统计次数：

int count = findRightBound(arr, target) - findLeftBound(arr, target);

3. 处理不存在的元素

如果目标元素不在数组中，lower_bound 和 upper_bound 返回相同位置，差值为0，因此无需额外判断，结果自然为0。手动实现时也具备同样特性。

基本上就这些方法。利用有序性加二分查找是这类问题的标准解法，既简洁又高效。