使用二分查找通过lower_bound和upper_bound确定左右边界，其差值即为目标元素出现次数，时间复杂度O(log n)，代码简洁高效。
在C++中统计有序数组中某个元素的出现次数，可以利用数组的有序特性，使用二分查找来高效定位目标元素的左右边界，从而计算出其出现次数。这种方法时间复杂度为 O(log n)，远优于暴力遍历的 O(n)。
1. 使用 lower_bound 和 upper_bound
C++提供了 std::lower_bound 和 std::upper_bound，非常适合处理有序数组：
- lower_bound 返回第一个不小于目标值的迭代器
- upper_bound 返回第一个大于目标值的迭代器
- 两者之差即为目标元素的出现次数
示例代码：
#include <vector> #include <algorithm> #include <iostream> <p>int countOccurrences(const std::vector<int>& 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; }</p><p>int main() { std::vector<int> arr = {1, 2, 2, 2, 3, 4, 5}; int target = 2; std::cout << target << " 出现了 " << countOccurrences(arr, target) << " 次n"; return 0; }</p>
登录后复制
2. 手动实现二分查找
如果不使用STL函数，也可以手动实现二分查找来找到左右边界：
立即学习“”；
查找左边界：
即构数智人是由即构科技推出的AI虚拟数字人视频创作平台，支持数字人形象定制、短视频创作、数字人直播等。
36 int findLeftBound(const std::vector<int>& 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<int>& 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。手动实现时也具备同样特性。
基本上就这些方法。利用有序性加二分查找是这类问题的标准解法，既简洁又高效。
以上就是++中如何统计有序数组中元素出现次数_c++有序数组元素出现次数统计的详细内容，更多请关注php中文网其它相关文章！
相关标签：
微信扫一扫打赏
支付宝扫一扫打赏
