Maison > développement back-end > C++ > le corps du texte

Dans le programme C, traduisez la requête de plage de tableau avec des éléments de même fréquence

WBOY
Libérer: 2023-09-09 20:45:12
avant
1419 Les gens l'ont consulté

Dans le programme C, traduisez la requête de plage de tableau avec des éléments de même fréquence

Ici, nous verrons une question intéressante. Nous avons un tableau avec N éléments. Nous devons exécuter une requête Q comme suit :

Q(start, end) signifie que du début à la fin, le nombre « p » apparaît exactement « p » fois. p>

Donc, si le tableau ressemble à : {1, 5, 2, 3, 1, 3, 5, 7, 3, 9, 8} et que la requête est -

Q(1, 8) - ici 1 apparaît une fois, 3 apparaît 3 fois. La réponse est donc 2

Q(0, 2) - où 1 apparaît une fois. La réponse est donc 1

algorithme

requête(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
Copier après la connexion

exemple

#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;
   }
}
Copier après la connexion

sortie

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
Copier après la connexion

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

source:tutorialspoint.com
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal