A - это массивы: определите, есть ли два целых числа, которые присутствуют в A одинаковое количество раз

Question

Например: A=[1,2,2,3,4,4,5]->true; А =[1,2,2,3,3,3,4,4,4,4]-> ложь.

proc(A){
list = newList()
for (i=1 to length[A]) {
   occ = 0
   n = a[i]
   for (j = 1 to length[A]) {
       if(a[j] == n)
            occ++
    } 
    list.append(occ)
}

но не работает, потому что в списке будут повторяться элементы. Я думал об использовании алгоритма, похожего на countingSort, но я не знаю длину вспомогательного вектора.

Любая помощь? В псевдокоде все будет хорошо. Спасибо.

Answer 1

С использованием структур данных, таких как map и set, эта задача может быть выполнена очень легко.

Algorithm:-
-> Loop through the array and store it in hashmap with key as the value of the array element and value as the count of it's occurrence.
-> Create an empty set
-> Loop through the map and keep storing the value of every key in the set and if somewhere in between looping u come across any value that's already there in the set, then return true else if u reach the end of map, then return false.

Давайте теперь посмотрим как псевдокод.

Pseudocode:-
-> we have input array as arr and length n
-> we create an empty map - m[int, int]
-> for (i -> 0 to n-1)
   {
      m[arr[i]]++;
   }
-> This in the end will give us our map which we want with key as the array element and value as it's count
-> create a set - s
-> iterate over map m as key -> value
   {
      if (value present in s) {
         return true
      }
      s.insert(value)
    }
-> If we reach here then it means we never came across any pair of elements whose occurrence is same, so return false.

Надеюсь это поможет!