создание алгоритма для поиска повторяющихся значений массива

Question

Я создал алгоритм псевдокода, чтобы найти повторяющиеся значения массива, который включает числа с плавающей запятой:

mergeSort(A);  
int i <- 0
for i<- A.lenght-1
  if Arr[i] == A[i+1]
          return A[i]
          while A[i] = A[i+1]
                i++
else
    i++

Я хочу изменить вышеупомянутый алгоритм, чтобы найти повторяющиеся значения и количество повторений.Я создал следующий алгоритм:

mergeSort(A); 
HashMap hashMap;
Int result <-0 int i <- 0
for i<- A.lenght-1
    int j <- 0
    if A[i] == A[i+1]
          j <- j+1
          result <- A[i]
          while A[i] == A[i+1]
             i <- i+1
             j<- j+1
         hashMap.insert(result , j)
      else
         i++
return hashMap

Это эффективный алгоритм?Это хороший способ использовать хэш-карту?

Answer 1

Будьте осторожны, числа с плавающей точкой не являются точными типами, и оператор равенства может возвращать неправильные значения. Для значений с плавающей запятой предпочитают тест | f1-f2 |

Answer 2

Вы можете просто использовать HashMap и сделать что-то вроде этого:

HashMap hash;
for (int i = 0; i < A.lenght; i++){
    value = hash.get(A[i]); 
    if (value == null) // is the first time that we find A[i]
        hash.put(A[i], 1);
    else    // A[i] is a duplicate
        hash.put(A[i], value + 1);
}

средний случай = O(n)

Я согласен с pboulanger: обратите внимание на сравнение с плавающей точкой.

Answer 3

Другой вариант - сохранить результат в парах ArrayList из [value count], это, вероятно, немного более эффективно, здесь действительно нет необходимости в HashMap.Я практически ничего не знаю о Java, но вы должны быть в состоянии написать что-то вроде:

arrayList.add(new Pair(result, j));