
Di sini kita akan melihat soalan yang menarik. Kami mempunyai tatasusunan dengan elemen N. Kita perlu melaksanakan pertanyaan Q seperti berikut:
Q(mula, tamat) bermakna dari mula hingga akhir, nombor "p" muncul tepat "p" kali. p>
Jadi jika tatasusunan kelihatan seperti: {1, 5, 2, 3, 1, 3, 5, 7, 3, 9, 8}, dan pertanyaannya ialah -
Q(1, 8) - di sini 1 muncul sekali , 3 muncul 3 kali. Jadi jawapannya ialah 2
Q(0, 2) - di mana 1 muncul sekali. Jadi jawapannya ialah 1
algoritma
pertanyaan, e) -
1 2 3 4 5 6 7 8 9 | Begin
get the elements and count the frequency of each element ‘e’ into one map
count := count + 1
for each key-value pair p, do
if p.key = p.value, then
count := count + 1
done
return count ;
End
|
Salin selepas log masuk
contoh
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | # include <iostream>
# include <map>
using namespace std;
int query(int start, int end , int arr[]) {
map<int, int> freq;
for (int i = start; i <= end ; i++)
freq[arr[i]]++;
int count = 0;
for (auto x : freq)
if (x.first == x.second)
return count ;
}
int main() {
int A[] = {1, 5, 2, 3, 1, 3, 5, 7, 3, 9, 8};
int n = sizeof(A) / sizeof(A[0]);
int queries[][3] = {{ 0, 1 },
{ 1, 8 },
{ 0, 2 },
{ 1, 6 },
{ 3, 5 },
{ 7, 9 }
};
int query_count = sizeof(queries) / sizeof(queries[0]);
for (int i = 0; i < query_count; i++) {
int start = queries[i][0];
int end = queries[i][1];
cout << "Answer for Query " << (i + 1) << " = " << query(start, end , A) << endl;
}
}
|
Salin selepas log masuk
output
1 2 3 4 5 6 | Answer for Query 1 = 1
Answer for Query 2 = 2
Answer for Query 3 = 1
Answer for Query 4 = 1
Answer for Query 5 = 1
Answer for Query 6 = 0
|
Salin selepas log masuk
Atas ialah kandungan terperinci Dalam program C, terjemah pertanyaan julat tatasusunan dengan elemen dengan kekerapan yang sama. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!