Jak znaleźć 2 najbardziej oddalone, różne od siebie, liczby w ciągu?

Tak jak w temacie. Na wejściu podany jest pewien ciąg liczb naturalnych i trzeba znaleźć 2 najbardziej oddalone, różne liczby. Bardzo proszę o szybkie rozwiązanie (oczywiście pod względem złożoności czasowej :)).

Szybki pomysł: wpierw sprawdzamy czy pierwsza i ostatnia są różne, potem druga i ostatnia, potem druga i przedostatnia, potem trzecia i przedostatnia,...
Edit, zły pomysł.

Pierwsza myśl: posortować liczby i zwrócić pierwszy oraz ostatni element (ew.pierwszy i przedostatni, jeżeli są identyczne itd.).
Złożoność czasowa będzie identyczna jak złożoność sortowania.

---

Edit: może `min` oraz `max` z tablicy wystarczy? Nie jestem pewien, czy poprawnie rozumiem to zadanie, ale jeżeli tak, to powinno być najlepsze wyjście :P

Ja mam rozwiązanie klasy "z armaty do muchy" ale ze średnim O(n) :P

• Ładujemy cały ciąg do hashmapy liczba -> lista pozycji gdzie wystąpiła (O(n))
• z każdej takiej listy wyciągamy min i max (znów O(n))
• wyciągamy najmniejszego mina i największego maxa (pesymistycznie O(n)), odległość to ich różnica a liczby to te którym odpowiada ten min i max ;]

A czemu po prostu nie tak?

const unsigned int N = 100;
unsigned int tab[N] = { 1, 2, 3, ... ,423 ,1, 23};
unsigned int min, max;
min = max = tab[0];
for(int i = 0; i < N; i++)
{
if(tab[i] < min) { min = tab[i]; continue; }
if(tab[i] > max) {max = tab[i];}
}
unsigned int result = max - min;

Głupek napisał(a):

A czemu po prostu nie tak?

const unsigned int N = 100;
unsigned int tab[N] = { 1, 2, 3, ... ,423 ,1, 23};
unsigned int min, max;
min = max = tab[0];
for(int i = 0; i < N; i++)
{
if(tab[i] < min) { min = tab[i]; continue; }
if(tab[i] > max) {max = tab[i];}
}
unsigned int result = max - min;

//EDIT: Dobra, już zczaiłem że chodziło mu o coś innego :D

Bo nie o to chodzi. Nie szukamy największej różnicy między liczbami w tablicy. Szukamy największej różnicy między indeksami różniących się liczb.

Wydaje mi się, że takie rozwiązanie będzie poprawne (i jednocześnie w pesymistycznym czasie O(n)).

Niech dana będzie tablica a[0..n - 1]. Na początku weźmy sobie dwa skrajne elementy. Czyli a[0] i a[n - 1]. Jeżeli są różne to zwracamy indeksy 0 i n - 1, jeżeli nie to niech b = a[0] = a[n - 1]. Teraz porównujemy z b liczby a[1], a[n - 2], a[2], a[n - 3]... aż któraś z liczb będzie różna b lub wskaźniki na indeksy się miną (wtedy ciąg jest stały). Jak znajdziemy wskaźnikiem po lewej stronie to zwracamy n - 1 - lewy_wskaźnik, a jak po prawej to prawy_wskaźnik.

Dlaczego to działa?
Załóżmy, że a[0] = a[n - 1] (w przeciwnym przypadku rozwiązanie jest oczywiste). Zauważmy, że b = a[0] musi być w parze będącej wynikiem, ponieważ jeżeli by jej nie było, to by oznaczało, że wewnątrz istnieje para c, d (załóżmy bez straty ogólności, że c < d), gdzie b != a[c] != a[d], wtedy d - c > n - 1 - c lub d - c > d, ale d - c > n - 1 - c <=> d > n - 1, sprzeczność, a d - c > d <=> c < 0, znowu sprzeczność.

Mogłem się gdzieś pomylić lub źle zrozumieć, piszcie wtedy.

Edit: Jak tak teraz sobie myślę, to czasami przydałby się LaTeX na forum.