trouver la fréquence dans un tableau en utilisant un vecteur

Question

Comment puis-je modifier mon code pour obtenir un compte pour chaque élément ? Avec mon code, tout va bien. Et il fonctionne, mais comment puis-je changer seulement cette partie ?

   #include <iostream>
   #include <vector> 

   void countFreq(int arr[], int n) 
   { 
      // Mark all array elements as not visited 
      std::vector<bool> visited(n, false); 

     // Traverse through array elements and 
     // count frequencies 
      for (int i = 0; i < n; i++) { 

      // Skip this element if already processed 
       if (visited[i] == true) 
            continue; 
      // Count frequency 
       int count = 1; 
       for (int j = i + 1; j < n; j++) { 
           if (arr[i] == arr[j]) { 
               visited[j] = true; 
               count++; 
              }  
      } 
       std::cout<<count<<" ";     
    } 
   } 

   int main() 
   { 
    int n;
    std::cin>>n;
    int arr[n];
    for(int i = 0; i < n; i++){
        std::cin>>arr[i];
    }
    countFreq(arr, n); 
    return 0; 
   } 

Et à propos du résultat`

input 10
      1 1 2 2 3 3 4 4 5 5

output 2 2 2 2 2

mais je veux obtenir

 output 2 2 2 2 2 2 2 2 2 2

(pour chaque élément)

Answer 1

Vous pouvez trouver les fréquences des nombres de cette façon si vous savez quel est l'élément maximum dans le tableau d'entrée. Disons que m est le nombre maximum dans votre tableau. donc vous devez créer un nouveau tableau de taille m . vous pouvez simplement les relier entre eux comme m seaux. de 0 à m. Et chaque seau contiendra le compte de chaque élément dans le tableau d'entrée. L'index de chaque seau fera référence à l'élément dans le tableau d'entrée. La complexité temporelle est de O(1) si nous savons quel est l'élément maximum du tableau.

Vous pouvez le faire de cette façon :

std::vector<int> frequencey(std::vector<int>& nums){
    auto max = *(std::max_element(nums.begin(), nums.end()));
    std::vector<int> frequencies(max + 1, 0);
    for(int i = 0; i < nums.size(); ++i){
        frequencies[nums[i]] +=1;
    }

    return frequencies;
}

Answer 2

Vous devez enregistrer le résultat dans un tableau pour chaque nombre. Ensuite, lorsque vous trouvez un numéro traité, vous imprimez le compteur à partir du tableau sauvegardé.

#include <iostream>
#include <vector>
#include <unordered_map>

void countFreq(int arr[], int n)
{
    // Mark all array elements as not visited
    std::vector<bool> visited(n, false);
    std::unordered_map<int, int> counter;

    // Traverse through array elements and
    // count frequencies
    for (int i = 0; i < n; i++)
    {

        // Skip this element if already processed
        if (visited[i] == true)
        {
            std::cout << counter[arr[i]] << " ";
            continue;
        }
        // Count frequency
        int count = 1;
        for (int j = i + 1; j < n; j++)
        {
            if (arr[i] == arr[j])
            {
                visited[j] = true;
                count++;
            }
        }
        counter[arr[i]] = count;
        std::cout<<count<<" ";
    }
}

int main()
{
    int n;
    std::cin>>n;
    int arr[n];
    for(int i = 0; i < n; i++)
    {
        std::cin>>arr[i];
    }
    countFreq(arr, n);
    return 0;
}

Answer 3

Votre fonction contient du code supplémentaire qui finit par vous dérouter. Le site visited est essentiellement inutile. Démarrez le count à l'adresse 0 et ne faites pas de cas particulier pour la cellule "actuelle" et vous verrez qu'un code très simple fera ce dont vous avez besoin :

void countFreq(int arr[], int n) 
{ 
    // Traverse through array elements and 
    // count frequencies 
    for (int i = 0; i < n; i++) { 

        // Count frequency 
        int count = 0; 
        for (int j = 0; j < n; j++) { 
            if (arr[i] == arr[j]) { 
                count++; 
            }  
        }

        std::cout << count << " ";     
   } 
}

Answer 4

Le problème est que vous écartez les valeurs déjà visitées.

Une possibilité est plutôt de mémoriser le compte lorsque la valeur est visitée la première fois, et de mémoriser la valeur de l'indice de la première apparition de la valeur, lorsqu'une valeur est visitée la 2ème, 3ème ... fois.

#include <iostream>
#include <vector> 

void countFreq(const std::vector<int>& arr) { 
   int n = arr.size();
      // Mark all array elements as not visited 
   std::vector<int> mem_count(n, n); 

     // Traverse through array elements and 
     // count frequencies 
    for (int i = 0; i < n; i++) { 

      // Skip this element if already processed 
        if (mem_count[i] != n) {
            std::cout << mem_count[mem_count[i]] << " ";
            continue; 
        }
        // Count frequency 
        int count = 1; 
        for (int j = i + 1; j < n; j++) { 
            if (arr[i] == arr[j]) { 
                  mem_count[j] = i; 
                  count++; 
            }  
        }
        mem_count[i] = count;
        std::cout << count << " ";     
    } 
} 

int main() { 
    int n;
    std::cin>>n;
    std::vector<int> arr(n);
    for(int i = 0; i < n; i++){
        std::cin >> arr[i];
    }
    countFreq(arr); 
    return 0; 
}

Answer 5

C'est très simple

#include <vector>
#include <map>
#include <iostream>

void main()
{
    std::vector<int> v { 1,1,2,2,3,3,4,4,5,5 }; // Your input vector

    // Count "frequencies"
    std::map<int, int> m;
    for (auto i : v)
        m[i]++;

    // Print output
    for (auto i : v)
        std::cout << m[i] << " ";
}