資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝學
法學C++中大於和小於查詢
在這篇文章中，我們給出一個問題，我們得到一個數組，我們需要回答兩種型別的查詢。
- 型別0 - 我們必須計算大於或等於x（給定值）的元素個數。
- 型別1 - 我們必須計算嚴格大於x（給定值）的元素個數。
這是一個簡單的例子：
Input : arr[] = { 10, 15, 30 , 40, 45 } and Q = 3
Query 1: 0 50
Query 2: 1 40
Query 3: 0 30
Output :
0
1
3
Explanation:
x = 50, q = 0 : No elements greater than or equal to 50.
x = 40, q = 1 : 45 is greater than 40.
x = 30, q = 0 : three elements 30, 40, 45 are greater than or equal to 30.尋找解決方案的方法
我們可以使用兩種不同的方法來尋找解決方案。首先，我們將使用暴力求解方法，然後檢查它是否適用於更高的約束條件。如果不是，那麼我們繼續最佳化我們的解決方案。
暴力求解法
在這種方法中，我們將遍歷所有q個查詢的陣列，並找到滿足給定條件的數字。
示例
#include <bits/stdc++.h>
using namespace std;
void query(int *arr, int n, int type, int val) {
int count = 0; // answer
if(!type) { // when type 0 query is asked
for(int i = 0; i < n; i++) {
if(arr[i] >= val)
count++;
}
} else { // when type 1 query is asked
for(int i = 0; i < n; i++) {
if(arr[i] > val)
count++;
}
}
cout << count << "\n";
}
int main() {
int ARR[] = { 10, 15, 30, 40, 45 };
int n = sizeof(ARR)/sizeof(ARR[0]); // size of our array
query(ARR, n, 0, 50); // query 1
query(ARR, n, 1, 40); // query 2
query(ARR, n, 0, 30); // query 3
return 0;
}輸出
0 1 3
在上述方法中，我們只是簡單地遍歷陣列並計算查詢的答案；這種方法適用於給定的示例，但是如果我們遇到更高的約束條件，這種方法將會失敗，因為程式的整體時間複雜度為O(N*Q)，其中N是陣列的大小，Q是查詢的數量，所以現在我們將最佳化這種方法，使其也適用於更高的約束條件。
高效方法
在這種方法中，我們將使用二分查詢來查詢給定值的上下界。我們首先使用二分查詢對陣列進行排序，然後根據需要應用我們的下界和上界函式。
示例
#include <bits/stdc++.h>
using namespace std;
void lowerbound(int *arr, int n, int val) {
int l = -1, r = n;
while(r - l > 1) { // binary searching the answer
int mid = (l+r)/2;
if(arr[mid] >= val)
r = mid;
else
l = mid;
}
if(r == n) // if r is unmoved then it means there is no element that satisfy the condition
cout << "0\n";
else
cout << n - r << "\n";
}
void upperbound(int *arr, int n, int val) {
int l = -1, r = n;
while(r - l > 1) { // binary searching the answer
int mid = (l+r)/2;
if(arr[mid] > val)
r = mid;
else
l = mid;
}
if(r == n)// if r is unmoved then it means there is no element that satisfy the condition
cout << "0\n";
else
cout << n - r <<"\n";
}
void query(int *arr, int n, int type, int val) {
if(!type) // if type == 0 we call lower bound function
lowerbound(arr, n, val);
else // if type == 1 we call upperbound function
upperbound(arr, n, val);
}
int main() {
int arr[] = { 1, 2, 3, 4 };
int n = sizeof(arr)/sizeof(arr[0]); // size of our array
sort(arr, arr+n); // sorting the array
query(arr, n, 0, 5); // query 1
query(arr, n, 1, 3); // query 2
query(arr, n, 0, 3); // query 3
return 0;
}輸出
0 1 2
上面的程式碼基於二分查詢，大大降低了時間複雜度。因此，我們的最終複雜度變為**O(NlogN)**，其中N是陣列的大小。
上述程式碼的解釋
在這種方法中，我們將使用二分查詢來查詢給定值的上下界。現在對於二分查詢，我們首先對陣列進行排序，因為它只適用於排序陣列。我們建立下界和上界函式，幫助我們分別找到滿足型別0、型別1條件的第一個數字，現在我們已經對陣列進行了排序。我們找到了滿足條件的第一個數字，所以此元素之後的元素也滿足條件，因此我們列印此元素的索引與N（陣列大小）的差值。
結論
在本文中，我們解決了一個問題，使用二分查詢解決大於和小於的查詢。我們還學習了這個問題的C++程式以及我們解決這個問題的完整方法（普通方法和高效方法）。我們可以用C、Java、Python和其他語言編寫相同的程式。希望本文對您有所幫助。
更新於：2021年11月26日
417 次瀏覽
廣告