Jak w temacie. Chciałbym się dowiedzieć w jaki sposób można byłoby pozbyć się duplikatów z tablicy jednowymiarowej algorytmem o złożoności O(n^2). Czy potrzeba najpierw taką tablice posortować?
Jeśli chodzi o O(n^3) to nie ma problemu.
private int size;
private int[] a=new int[size];
private int nElems;
public void noDups() //metoda usuwa duplikaty z tablicy (z kilku elementów o tej samej wartości
{ //O(n^3)
int p,q; //zmienne pomocnicze do przechowywania indeksu elementów tablicy
p=0;
while(p<nElems) //zmienne p wskazuje po kolei na każdy element tablicy
{
q=p+1; //natomiast zmienna q wskazuje na element o jeden dalej niż p
while(q<nElems)
{
if(a[p] == a[q]) //jeśli element wskazywany przez p jest taki sam jak
delete(q); //element wskazywany przez indeks q to usuwamy element a[q]
else
q++; //zwiększenie indeksu q
}
p++; //zwiększenie indeksu p
}
}