Optymalizacja algorytmu

Cześć,

miałem wczoraj robiony test rekrutacyjny przy pomocy Codility. Z 4 pytań 3 zrobiłem prawidłowo, ale czwarte mnie pokonało.

Zadaniem było zoptymalizować następujący algorytm:

class Solution {
    public int solution(int[] A) {
        int N = A.Length;
        int result = 0;
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                if (A[i] == A[j])
                    result = Math.Max(result, Math.Abs(i - j));
        return result;
    }
}

Nie potrafiłem wymyślić jak to napisać poprawniej.

Czy ktoś może mnie nakierować? Nie chcę otrzymać od Was gotowego rozwiązania, a raczej nakierowania na odpowiednie tory.

Na C# się nie znam, ale na początek bym to zmienił tak

class Solution {
    public int solution(int[] A) {
        int N = A.Length;
        int result = 0;
        int N_1 = N - 1;
        for (int i = 0; i < N_1; i++)
            for (int j = i + 1; j < N; j++) 
              if (A[i] == A[j]) {
                int d = j - i;
                if (result < d) result = d;
              }
        return result;
    }
}

jeśli dobrze rozumiem to ten kod szuka dwóch identycznych liczb w tablicy maksymalnie oddalonych od siebie.
Ale można by ten kod całkiem przeorać i sprawdzać najpierw oddalone od siebie liczby o N-1 potem o N-2, N-3 i tak aż do 1. Wtedy pierwsze znalezienie kończyłoby szukanie

Zadanie polega na znalezieniu w zadanej tablicy maksymalnej odległości par liczb, które są sobie równe.
Na przykład dla: A = [0, 2, 5, 7, 3, 1, 5, 7, 3, 2, 3] pary takich liczb to:

• (1, 9), bo A[1] == A[9] == 2,
• (2, 6), bo A[2] == A[6] == 5,
• (3, 7), bo A[3] == A[7] == 7,
• (4, 8), (4, 10), (8, 10), bo A[4] == A[8] == A[10] == 3

Wynikiem działania na tym przykładzie powinna być liczba 8, bo max( abs(1-9), abs(2-6), abs(3-7), abs(4-8), abs(4-10), abs(8-10) ) = 8

Algorytm nie jest optymalny, bo sprawdza liczby każda z każdą dwukrotnie, np. robi porównanie A[2] == A[5], a potem A[5] == A[2]. Ponadto sprawdza elementy o tym samym indeksie, np. A[4] == A[4], co jest bez sensu. Modyfikacja warunku pętli pozwoli ograniczyć ilość tych porównań do wymaganego minimum (edit: właściwie nie warunku, a wartości początkowej).

Edycja:
Wpadłem na jeszcze jeden pomysł. Wewnętrzną pętlę można zaczynać od momentu i + 1 + result. Pomijamy wtedy wyniki mniejsze od dotychczas znalezionego.

trzeba pierwsza pętle lecieć od początku a drugą pętle od końca kolekcji jeśli coś znajdziesz to to zapisujesz indeks i w następnej iteracji szukasz tylko wyższe od tego zapisanego indeksu

Przeorane rozwiązanie w Javie (bo jak mówiłem C# nie znam). Pierwsze znalezienie kończy przeszukiwanie

public class Solution {

     public static void main(String []args) {
        final int[] array = {0, 2, 5, 7, 3, 1, 5, 7, 3, 2, 3};
        System.out.println("diff = " + solution(array)); 
     }
     
    private static int solution(int[] array) {
        final int length = array.length;
        final int length1 = length - 1;
        for (int diff = length1; 1 <= diff; diff -= 1) 
            for (int index = diff; index <= length1; index += 1) 
                if (array[index - diff] == array[index]) 
                    return diff;
        return 0;
    }
}

Tak na szybko patrząc, wydaje mi się, że da się to zrobić w jednorazowym przebiegu, ale z pomocą 1 hashmap/dict/map czy co to tam w C# jest + dodatkowej zmiennej trzymającej największa odległość pomiędzy indeksami ej samej wartości.

Algorytm:

Iterujemy po liście i teraz:

1. Hashmapa przechowuje numer liczby jako klucz, a wartością klucza są numery indeksów tablicy po przecinku, gdzie tę liczbę znaleziono, ale nie wszystkie. Przechowujemy tam tylko dwa "skrajne" indeksy. Czyli, jeżeli za przykład weźmiemy 3, wtedy mamy ją na pozycjach [4,8,10], wówczas tej hashmapie powinniśmy mieć 3 => [4,10], czyli jeśli pozycji danej liczby jest więcej niż 2, to zostawiamy skrajne wartości i wyciągamy tą "odległość" odejmując większą wartość od mniejszej. Jeśli wystąpień liczby jest mniej niż 2 to wiadomo.

2. Druga zmienna "pamięta" poprzednio obliczoną największą odległość, jeśli sytuacja wynikła z działania w pkt 1) ulegnie zmianie, wówczas wskazuje ona na tą nową wartość obliczoną

Wszystko do mapy
key - liczba w tablicy
value - index liczy w tabeli (pozycja na której po raz pierwszy wystąpiła)

"akcja" podejmowana "ifExists(key)" -- odczytać na jakiej pozycji pierwszy raz wystąpiła liczba kucz, to nasz lokalny max
Jeżeli lokalny max > globalny maxSoFar to maxSoFar = localMax

TLDR;
połączenie idei hashmap z wrzuceniem do niej wszystkich liczb z tablicy + lokalny max porównać i aktualizować z maxSoFar (jak jeden przebieg w SelectionSort)
Całość O(n)

Hint1
W tego typu 'kodo-rekrutacjach', jak nie mamy O(n) to nie jest OK. Takie tematy: przerób O(n^2) na O(n)

Hint2
O(n) + O(n) daje O(n) i nie patrzymy, że operacji w pętli będzie więcej. Liczy się O

Hint3
Trzeba się tych zadań trochę natrzaskać i zapodać sobie solidną powtórkę z ASD bo z codziennymi taskami mają one niewiele wspólnego.

public int solution(int[] A) {
            Dictionary<int, int[]> dict = new Dictionary<int, int[]>();
            int res = 0;
            for (int i = 0; i < A.Length; i++)
            {
                if (dict.ContainsKey(A[i]))
                {
                    var t = dict[A[i]];
                    t[1] = i;
                    if (res < t[1] - t[0])
                        res = t[1] - t[0];

                }
                else
                {
                    dict.Add(A[i], new []{i,0});
                }
            }

            return res;
        }

Czy coś takiego to będzie bardziej optymalne?

@szydlak:

Nie wiem co to jest, nie znam C#, .NET
dict.Add(A[i], new []{i,0});

Ale jak dodasz przy pierwszym wystąpieniu klucza int z jego pozycją to masz wszystko co potzrebujesz.
Każde natępne wystąpienie, drugie, trzecie, czwarte będzie jeszcze "bardziej na prawo" w tablicy od drugiego, więc nie interesuje cię jaka była 'metryka: 1-sze i 2-gie wystąpienie, bo trzecie ma na pewno bardziej oddalony index od drugiego wystąpienia.

@maszrum: wyjaśnił i podał rozwiązanie: "Zadanie polega na znalezieniu w zadanej tablicy maksymalnej odległości par liczb, które są sobie równe."

W zadaniu przykładzie result to int a nie tablica, więc interesuje nas wynik -- jedna wartość int.

Wracając do 2-go, 3-go wystąpienie.
Jeżeli dla tego konkretnego klucza, np. liczby 7 obecna odległość jest większa od wcześniej znalezionych 5-tek, to result = ta odległość.
Noc więcej ne trzeba zapamiętywać, tylko "max so far" kolejno dla elementów tablicy.

Analogia: jeden przebieg Selection Sort

Live:
w array mam teraz 7 z array[15]
HashMap ma już zapiany ten klucz i value zwraca 3 (pierwszy raz by array[3] = 7)
15-3 = 12 Nie potrzeba zapisywać pozycji tego wystąpienia 7-ki
Czy wcześniej dla np. klucza 5 dwie piątki były w 'odległości" result = 9?
Tak? Nasz result = 12 Nie potrzeba zapisywać jaka para liczb dała taki wynik
Nie? Cały czas 5-tli mają największy dystans.

Nic więcej nie trzeba trzymać w HashMap (lub jak się w C# mapa nazywa)

Rozwiązanie w Scali:

object kobi55 {
  def main(args: Array[String]): Unit = {
    val a = Array(0, 2, 5, 7, 3, 1, 5, 7, 3, 2, 3)
    val result = a.zipWithIndex
      .groupBy(_._1)
      .toList
      .map(_._2.map(_._2))
      .map(indices => indices.max - indices.min)
      .+:(0)
      .max
    println(result)
  }
}

https://www.ideone.com/qI0row

public int solution(int[] A)
        {
            int N = A.Length;
            int result = 0;
            int index = 0;

            for (int i = 0; i < N; i++)
            {
                for (int j = N-1; j > i; j--)
                {
                    if (A[i] == A[j] && j > index)
                    {
                        result = Math.Max(result, Math.Abs(i - j));
                        index = j;
                    }
                }
            }

            return result;
        }

@Mateusz mat:

Zewnętrzna pętla n razy
Wewnętrzna pętla odpowiednio razy:
n-1
n-2
n-3
...
2
1

Da to w licząc łącznie pętla zewnętrzna i wewnętrzna n-1 + n-2 + n-3 + 2 + 1

Dla uproszczenia wszystkie przebiegi przez obie pętle razy: n , n-1, n-2, n-3,...3, 2, 1
Suma ciągu arytmetycznego da (1+n)/2 * n = (n^2 + n)/2
https://www.matemaks.pl/suma-ciagu-arytmetycznego.html

w twoim przypadku: a1 = 1, an = n

O((n^2 + n)/2) ~= O(n^2)

class Solution {
    public int solution(int[] A) {
        int N = A.Length;
        Dictionary<int, int> front = new Dictionary<int, int>();
        Dictionary<int, int> back = new Dictionary<int, int>();

        int result = 0;
        for (int i = 0; i < N / 2; i++) {
            int j = N - 1 - i;
            front.TryAdd(A[i], i);
            back.TryAdd(A[j], j);

            result = Math.Max(result, back[A[i]] - i);
            result = Math.Max(result, j - front[A[j]]);

            if (result >= j) return result;
        }
        return result;
    }
}

    int findMaxDistance(Integer[] arr) {

        Map<Integer, Integer> indices = new HashMap<>();
        int maxDistance = 0;

        for (int i = 0; i < arr.length; i++) {

            indices.putIfAbsent(arr[i], i);

            int pairDistance = i - indices.get(arr[i]);
            if (pairDistance > maxDistance) {
                maxDistance = pairDistance;
            }
        }

        return maxDistance;
    }

Do przerobienia z Java na C#
Map, HashMap to mapa key i value typu integer
putIfAbsent to java syntactic sugar do zastąpienia przez klasyczne if(map.get(key) == null){map.put(key, value)} lub od razu przez to co oferuje C#, .NET