首頁 > 後端開發 > C++ > 主體

在C程式中,將數組範圍查詢與頻率相同的元素進行翻譯

WBOY
發布: 2023-09-09 20:45:12
轉載
1391 人瀏覽過

在C程式中,將數組範圍查詢與頻率相同的元素進行翻譯

這裡我們會看到一個有趣的問題。我們有一個包含 N 個元素的陣列。我們必須執行一個查詢 Q,如下所示:

Q(start, end) 表示從開始到結束,數字「p」出現的次數剛好是「p」次。 p>

因此,如果數組類似於:{1, 5, 2, 3, 1, 3, 5, 7, 3, 9, 8},並且查詢為-

#Q(1 , 8) - 這裡1 出現一次,3 出現3 次。所以答案是 2

Q(0, 2) - 這裡 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
登入後複製

以上是在C程式中,將數組範圍查詢與頻率相同的元素進行翻譯的詳細內容。更多資訊請關注PHP中文網其他相關文章!

來源:tutorialspoint.com
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
最新問題
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板
關於我們 免責聲明 Sitemap
PHP中文網:公益線上PHP培訓,幫助PHP學習者快速成長!