資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
廣告