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 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告