Menulis lebih besar daripada dan tidak kurang daripada pertanyaan menggunakan C++

Dalam artikel ini, kita diberikan soalan, diberikan array, dan terdapat dua jenis pertanyaan untuk dijawab.

• Taip 0 - Kita perlu mengira bilangan elemen yang lebih besar daripada atau sama dengan x (nilai yang diberikan).
• Jenis 1 - Kita perlu mengira bilangan elemen yang lebih besar daripada x (nilai yang diberikan).

Jadi ini contoh mudah -

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.

Cara-cara untuk mencari penyelesaian

Terdapat dua kaedah berbeza yang boleh kita gunakan untuk mencari penyelesaian. Mula-mula kita akan menggunakan penyelesaian kekerasan dan kemudian semak sama ada ia berfungsi untuk kekangan yang lebih tinggi. Jika tidak berkenaan, maka kami terus mengoptimumkan penyelesaian kami.

Penyelesaian brute force

Dalam kaedah ini, kami akan mengulangi tatasusunan untuk semua pertanyaan q yang memenuhi syarat yang diberikan dan mencari nombor yang memenuhi syarat.

Contoh

#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;
}

Output

0
1
3

Dalam kaedah di atas, kita hanya mengulangi tatasusunan dan mengira jawapan kepada pertanyaan ini adalah sah untuk contoh yang diberikan, tetapi jika kekangan yang lebih tinggi dihadapi, kaedah ini akan gagal kerana jumlah kerumitan masa program ialah O(N*Q), di mana N ialah saiz tatasusunan dan Q ialah bilangan pertanyaan, jadi sekarang kami akan mengoptimumkan pendekatan ini supaya ia berfungsi untuk kekangan yang lebih tinggi.

Kaedah yang cekap

Dalam kaedah ini kita akan menggunakan carian binari untuk mencari sempadan atas dan bawah nilai yang diberikan. Kami mula-mula menyusun tatasusunan menggunakan carian binari dan kemudian menggunakan fungsi sempadan bawah dan atas kami seperti yang diperlukan.

Contoh

#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;
}

Output

0
1
2

Kod di atas menggunakan carian binari, yang sangat mengurangkan kerumitan masa. Oleh itu, kerumitan akhir kami ialah O(NlogN), dengan N ialah saiz tatasusunan.

Penjelasan kod di atas

Dalam kaedah ini, kita akan menggunakan carian binari untuk mencari sempadan atas dan bawah nilai yang diberikan. Sekarang untuk carian binari kami mengisih tatasusunan dahulu kerana ia hanya berfungsi pada tatasusunan yang diisih. Kami mencipta fungsi sempadan bawah dan sempadan atas untuk membantu kami mencari nombor pertama yang memenuhi syarat jenis 0 dan jenis 1. Kini kami telah menyusun tatasusunan. Kami mencari nombor pertama yang memenuhi syarat, jadi elemen selepas elemen ini juga memenuhi syarat, jadi kami mencetak perbezaan antara elemen itu dan indeks N (saiz tatasusunan).

Kesimpulan

Dalam artikel ini, kami menyelesaikan masalah menyelesaikan lebih daripada dan tidak kurang daripada pertanyaan menggunakan carian binari. Kami juga mempelajari program C++ untuk masalah ini dan pendekatan lengkap kami untuk menyelesaikannya (kedua-dua remeh dan cekap). Kita boleh menulis program yang sama dalam bahasa lain seperti C, Java, Python dan lain-lain. Harap anda mendapati artikel ini membantu.

Atas ialah kandungan terperinci Menulis lebih besar daripada dan tidak kurang daripada pertanyaan menggunakan C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!