[Algorytmy] Max oddalone od siebie równe wartości w tablicy

Awatar użytkownika
leg14
Użytkownik
Użytkownik
Posty: 3132
Rejestracja: 5 lis 2014, o 20:24
Płeć: Mężczyzna
Lokalizacja: Radom
Podziękował: 154 razy
Pomógł: 475 razy

[Algorytmy] Max oddalone od siebie równe wartości w tablicy

Post autor: leg14 » 8 lis 2017, o 20:02

Mamy daną tablicę liczb całkowitych \(\displaystyle{ A \left[ n \right]}\) i interesuje nas znalezienie \(\displaystyle{ \max \left\{ |i-j|:i,j \in \left\{ 0,...,n-1\right\};A \left[ i \right] =A \left[ j \right] \right\}}\). Jedyny pomysł jaki mi przychodzi do głowy (który nei jest chamskim \(\displaystyle{ O \left( n^2 \right)}\) to użycie dodatkowej pamięci:
tablicę \(\displaystyle{ A}\) sortujemy quick-sortem (otrzymując tablicę \(\displaystyle{ A'}\) i jednocześnie tworzymy tablicę \(\displaystyle{ B \left[ n \right]}\) taka, ze \(\displaystyle{ B \left[ i \right]}\) koduje, z której komórki \(\displaystyle{ A}\) przyszedł element \(\displaystyle{ A' \left[ i \right]}\). Jednocześnie nic nie tracąc możemy założyć, że jeśli \(\displaystyle{ A' \left[ i \right] =A' \left[ j \right]}\) to \(\displaystyle{ B \left[ i \right] < B \left[ j \right]}\) dla \(\displaystyle{ i<j}\). No i wtedy już łatwo można liniowo znaleźć to maksimum, czyli ostatecznie pamięciowo jest to \(\displaystyle{ O \left( n \right)}\), a obliczeniowo \(\displaystyle{ O \left( n \cdot \ln \left( n \right) \right)}\). Da się to zrobić szybciej? (pod względem obliczeń)
Ostatnio zmieniony 9 lis 2017, o 15:22 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.

Afish
Moderator
Moderator
Posty: 2828
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 356 razy

[Algorytmy] Max oddalone od siebie równe wartości w tablicy

Post autor: Afish » 9 lis 2017, o 15:22

Użycie słownika z hashowaniem daje liniowy czas.

ODPOWIEDZ