数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究使用 C++ 在排序数组中查找大于 k 的元素个数
在这个问题中，我们给定一个包含 N 个排序整数的数组 arr[] 和一个整数 k。我们的任务是在排序数组中查找大于 k 的元素个数。
让我们举个例子来理解这个问题，
输入
arr[] = {1, 2, 5, 7, 8, 9} k = 4输出
4
解释
Elements greater than k = 4 are 5, 7, 8, 9
解决方案方法
一个简单的解决方案是使用循环遍历数组从 0 到 N。然后在第一个大于 k 的元素处停止。然后计算剩余值的个数。
示例
程序说明了我们解决方案的工作原理
#include <iostream>
using namespace std;
int findGreaterCount(int arr[], int n, int k){
for(int i = 0; i < n; i++){
if(arr[i] > k)
return (n - i);
}
return -1;
}
int main(){
int arr[] = { 1, 3, 5, 7, 7, 8, 12, 21};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 5;
cout<<"The number of elements greater than k is "<<findGreaterCount(arr, n, k);
return 0;
}输出
The number of elements greater than k is 5
上面的代码运行良好，但程序的时间复杂度为 O(N)。
另一种更高效的方法是使用二分查找来查找大于 k 的元素。然后返回大于元素的计数。
示例
程序说明了我们解决方案的工作原理
#include <iostream>
using namespace std;
int findGreaterCount(int arr[], int n, int k){
int s = 0;
int e = n - 1;
int firstGreterEle = n;
while (s <= e) {
int mid = s + (e - s) / 2;
if (arr[mid] > k) {
firstGreterEle = mid;
e = mid - 1;
}
else
s = mid + 1;
}
return (n - firstGreterEle);
}
int main(){
int arr[] = { 1, 3, 5, 7, 7, 8, 12, 21};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 5;
cout<<"The number of elements greater than k is "<<findGreaterCount(arr, n, k);
return 0;
}输出
The number of elements greater than k is 5
更新于: 2022年2月14日
973 次浏览
广告