資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時裝學
法律學C 語言程式中針對頻率與值同等的元素的陣列範圍查詢
我們在這裡將看到一個有趣的問題。我們有一個包含 N 個元素的陣列。我們必須像下面那樣執行一個 Q 查詢 −
Q(start, end) 表示數字“p”在 start 到 end 的範圍內恰好出現了“p”次數。
因此，如果陣列為：{1, 5, 2, 3, 1, 3, 5, 7, 3, 9, 8}，並且查詢為 −
Q(1, 8) − 這裡數字 1 出現了 1 次，數字 3 出現了 3 次。因此，答案是 2
Q(0, 2) − 這裡數字 1 出現了 1 次。因此，答案是 1
演算法
query(s, e) −
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
例項
#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++) //get element and store frequency
freq[arr[i]]++;
int count = 0;
for (auto x : freq)
if (x.first == x.second) //when the frequencies are same, increase count count++;
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;
}
}輸出
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
更新於：02-07-2020
218 次瀏覽
廣告