Jak usunąć duplikaty algorytmem o złożoności O(n^2)?

0

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
       }
   }
1

Przepisać do zbioru (HashSet) i z powrotem do tablicy?

0

Najszybciej jak wiem, to można w O(n log n) to zrobić. 2 sposoby na to:

  1. używając set usuwasz wszystkie powtarzające się elementy (tworzenie zbioru O(n log n) i potem przepisać do tablicy O(n)
  2. posortować tablicę O(n log n) a następnie przejrzeć całą, przepisując tylko niepowtarzające się elementy (pierwszy w sekwencji) O(n)
0

Quicksort to właśnie pesymistycznie O(n^2).
Do tego dodajesz usunięcie duplikatów => O(n) czyli w efekcie końcowym pesymistycznie O(n^2).

Przy użyciu LinkedHashSet może być jeszcze szybciej.

0

O(n2). Wolne ale, chyba mozna tak po prostu:

  • iterujesz po kolejnych elementach
  • dla aktualnego elementu, usuwasz elementy dla aktualnej wartosci iterujac po wszystkich elementach

Jak chcesz szybciej to tak:

  • sortujesz, wszystkie duplikaty powinny byc kolo siebie (wydaje mi sie ze to jest najszybsze, ale nie mam 100% pewnosci) - tracisz oryginalna kolejnosc - najprosciej uzyc: std::sort i std::unique. O(n log n) (implementacja std::unique jest podana z grubsza na stronie, wiec mozesz tak samo zrobic - generalnie: iterujesz od poczatku do konca, j - iterujesz od poczatku ale ++ robisz tylko jesli NIE chcesz usunac elementu. Zawsze przed zwiekszeniem j robisz: tab[j] = tab[i];)
  • wrzucasz do seta (chyba naprosciej jak sie da, ale troche wolniej) O(n log n) ale z duza wieksza stala niz to wyzej,
  • w secie trzymasz elementy ktore juz wystapily i iterujesz (nie tracisz kolejnosci), j.w. ale jeszcze wieksza stala tyle ze nie tracisz kolejnosci

Jesli elementy sa z jakiegos znanego zbioru to mozesz wykorzystac sortowanie kubelkowe, wtedy masz zlozonosc O(n)

0

To jest niezły hardkor. Problem można dla ograniczonego zbioru zrobić pesymistycznie w O(n) za pomocą zliczania / kubełkowania. Dla dowolnego zbioru można to zrobić średnio w O(n) za pomocą HashMap/HashSet. Można to też zrobić dla dowolnego zbioru poprzez drzewa w O(nlogn) za pomocą TreeMap / TreeSet.
Najbardziej naiwny algorytm, polegający na:

  1. Wybieram liczbę z tablicy
  2. Przeglądam całą pozostałą tablicę w poszukiwaniu tej liczby
  3. Jeśli nie znalazłem to przepisuje do tablicy wynikowej
    Ma O(n2). I to jest ten sam algorytm który pokazałeś. I ma on O(n2) jeśli zamiast delete (które jak rozumiem działa u ciebie w O(n)) będziesz zapisywał sobie które elementy mają się znaleźć w tablicy wynikowej, bo takie zapisanie ma O(1) a potem przepisanie na koniec danych zrobisz w O(n), sumarycznie O(n2) + O(n) = O(n2)
0

http://ideone.com/BDtTsw

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	static int[] tab = new int[]{1, 2, 3, 1, 2, 5, 1, 8, 3};
    static int nElems = tab.length;
	public static void main (String[] args) throws java.lang.Exception
	{
		int newElems = 0;
		for (int i = 0, x = nElems; i < x; i++) {
			int v = tab[i];
			boolean duplicate = false;
			for (int j = 0; j < newElems; j++) {
				duplicate |= v == tab[j];
			}
			if (!duplicate) {
				tab[newElems] = v;
				newElems++;
			}
		}
		nElems = newElems;
		System.out.println(Arrays.toString(Arrays.copyOf(tab, nElems)));
	}
}

[1, 2, 3, 5, 8]

1 użytkowników online, w tym zalogowanych: 0, gości: 1