Znajdź ilość par

Robiłem dzisiaj zadanie rekrutacyjne na Codility, niestety nie zrobiłem screena, ale jego treść to +/- coś takiego. Mając int[] zwróć ilość par indeksów mających przypisaną tą samą wartość. Numer pierwszego indeksu musi być mniejszy niż jego pary czyli przy tablicy:

[0] = 1;
[1] = 2;
[2] = 0;
[3] = 1;
[4] = 1;

mamy 3 pary (0-3,0-4,3-4), ale już dla [4] nie ma pary. Dodatkowo tablica może mieć od 0 do 100000 liczb, a każda z nich >-1mld && <1mld. Napisałem coś takiego:

int counter = 0;
for(int i=0;i<arr.length;i++) {
	for(int j=i+1;j<arr.length;j++) {
		if(arr[i]==arr[j]) {
		counter++;
		}
	}
}

Sprawdziłem kilka spraw testowych z małym wolumenem i działało poprawnie. Na podsumowaniu jednak za performance dostałem całe 0% i tutaj pojawia się moje pytanie. Czy powyższe rozwiązanie pod względem wydajności jest tak beznadziejne? Jak później zacząłem się zastanawiać to może lepiej byłoby w drugiej pętli zrobić stream ze skipem już sprawdzonych elementów, zrobić filtr i zwrócić count.

Twoje rozwiązanie ma złożoność obliczeniową O(n^2), da się to zrobić w O(n).

Ok, czyli jest słabe. Podpowiedz mi tylko czy z wykorzystaniem samej tablicy czy tak jak wspomniałem kolekcji i streama albo konkretnej implementacji kolekcji i wykorzystanie jej właściwości?

Pomyśl o dodatkowej strukturze danych, aby zapisywać odwiedzone już elementy. Jeśli elementy są z przedziału 0 do N-1, to można zastosować trick pozwalający na nie korzystanie z dodatkowej pamięci.

Hint: na Codility zapomnij o streamach Javowych i innych luksusach, myśl w kategoriach algorytmów i struktur danych.

Mapa i int jako klucz i ilość wystąpień jako aktualizowana wartość?

Java to nie moja bajka, ale naskrobałem coś takiego: https://ideone.com/ALmcTJ

Klasyczne zadanie na hash mape

MarekR22 napisał(a):

Java to nie moja bajka, ale naskrobałem coś takiego: https://ideone.com/ALmcTJ

Tzn. da się to zrobić na HashMapie, ale ignorujesz powtórzenia. Według twojego rozwiązania dla tablicy [A, B, C] gdzie A=B=C=1 jest tylko jedna para, podczas gdy są trzy pary (A,B; A,C; B,C) czyli końcówka powinna wynosić:

        return m.values().stream()
                    .mapToInt(i -> i-1)
                    .sum();

A nie czasami tak?

class Task
{
    static long countPairs(int[] a)
    {
        int result = 0;
        HashMap<Integer, Integer> m = new HashMap<>();
        for (int x : a)
        {
            result += m.compute(x, (key, val) -> (val == null) ? 0 : val + 1);
        }
        return result;
    }
}

Bo jeżeli mamy np. int[10] i każdy element tablicy jest równy to możemy stworzyć łącznie sum = 9+8+...+0 par spełniających warunek i<j & int[i]==int[j].