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

使用二分查找通过lower_bound和upper_bound计算有序数组中目标元素的出现次数，时间复杂度O(log n)，示例代码展示了标准库方法与手动实现边界查找的两种方式，适用于已排序数组的高效统计。

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

在C++中统计有序数组中某个元素的出现次数，可以利用数组的有序性来提升效率。最直接有效的方法是使用二分查找定位目标元素的左右边界，从而计算出其总出现次数。

使用标准库 lower_bound 和 upper_bound

对于已排序的数组，std::lower_bound 返回第一个不小于目标值的迭代器，而 std::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 出现了 3 次。这种方法时间复杂度为 O(log n)，适合大规模数据。

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

手动实现二分查找获取边界

如果想更深入理解过程，也可以手动实现两个二分查找函数，分别找出目标元素的第一次和最后一次出现位置。

会译·对照式翻译

会译是一款AI智能翻译浏览器插件，支持多语种对照式翻译

下载

示例代码片段：

int findFirst(const std::vector& arr, int target) {
    int low = 0, high = arr.size() - 1;
    int result = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            result = mid;
            high = mid - 1; // 继续向左找
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return result;
}
int findLast(const std::vector& arr, int target) {
int low = 0, high = arr.size() - 1;
int result = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
result = mid;
low = mid + 1; // 继续向右找
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}
int countOccurrencesManual(const std::vector& arr, int target) {
int first = findFirst(arr, target);
int last = findLast(arr, target);
if (first == -1) return 0;
return last - first + 1;
}

这种方式逻辑清晰，便于调试和理解底层机制。