Java - tablice - wyeliminuj wszystkie powtórzenia elementów tablicy

Question

No właśnie. Jak wyeliminować wszystkie powtórzenia elementów tablicy?

Mój tok myślenia, czy jest poprawny?

Tworzymy zmienną do zliczania powtórzonych wyrazów, lecimy po tablicy po i (lecimy po tablicy po j, bo chcemy każdy wyraz z każdym) i porównujemy czy element tablicy i jest równy elementowi z j, jeśli tak to inkrementujemy zmienną do zliczania (jeśli zmienna wyjdzie zero to zwracamy niezmienioną tablicę)
i tworzymy nową tablicę o rozmiarze starej pomniejszony o ilość zliczonych powtórzeń

No właśnie, i jak teraz przekopiować te stare niepowtórzone wyrazy?

Comments

Czy to ma być taka postać?

int[] withRepeat = {1,1,4,5,6,7,8,8,1,2,3,4,5,6,7,8,9};

 

---

Tak

---

Jakiego typu operacje mogę wykonać? Sortowanie, kolekcje?

---

Jak najbardziej podstawowe: najlepiej (jeśli się da) tylko pętle, tablice. Mniej więcej ten poziom ;)

Answer 1

Jeśli chodzi o Jave to, że tak powiem dziś robi się to tak (streamami):

int[] tab = {1,1,1, 2,2, 3,3, 4,4,4, 5,5,5};

int[] uniques =Stream.of(tab).distinct().toArray();

Jeśli chodzi o opracowanie algorytmu to:

https://stackoverflow.com/questions/20180902/fastest-way-to-find-if-all-the-elements-of-an-array-are-distinct

Answer 2

public int[] removeDuplicates(int[] input) {
	Arrays.sort(input);
	int n = input.length;
	int[] tmp = new int[n];
	int j = 0; 
	for(int i = 0; i < n-1; ++i){
		if(input[i] != input[i+1]){
			tmp[j++] = input[i];
		}
	}
	tmp[j++] = input[n-1];
	int[] result = new int[j];
	for(int i = 0; i < j; ++i) {
		result[i] = tmp[i];
	}
	return result;
}

 

Answer 3

void zróbRóżnowartościową() {
	        boolean [] unique = new boolean[tablica.length];
	        int counter = 0;

	        for (int i = 0; i < unique.length; i++) {
	            unique[i] = true;
	            // wstępnie oznaczamy elementy na true
	        }

	        for(int i = 0; i < tablica.length; i++) {
	            for(int j = 0; j < i; j++) {
	                if(tablica[j] == tablica[i])
	                    unique[i] = false;
	                // powtarzające się elementy oznaczamy false
	            }
	            if(unique[i])
	                counter ++;
	            //tak długo jak jest tablica unique jest true, zwiększamy licznik - liczymy liczbę dobrych, niepowtórzonych elementów tej tablicy
	        }

	        int [] newtablica = new int[counter];
	        // tworzymy tablicę o rozmiarze licznika - dobrych elementów
	        int j = 0;
	        for (int i = 0; i < tablica.length; i++) {
	            if(unique[i]) { // jeśli unique jest true
	                newtablica[j] = tablica[i]; // zapisz w nowej tablicy
	                j++; // przechodzimy do kolejnego slotu w nowej tablicy
	            }
	        }
	        tablica = newtablica; // nasza tablica staje się nową tablicą
	    }

Zawsze może być takie rozwiązanie.

Answer 4

a dlaczego nie zamienisz sobie tej tablicy na Set? wtedy powtorzenia same się wyeliminują

Comments

takie zadanie :)

---

No to sprawdzaj czy wartości nie ma w pomocniczym secie i jeśli jest to eliminuj a jak nie ma to dodaj do set'a. BTW. typowe zadanie na rekrutacjach :)

---

Nie napisałeś czy można sortować taką tablicę czy nie bo wtedy można sobie utworzyć tablicę na początku i wtedy iterując po takiej posortowanej tablicy możesz patrzyć czy obecny element jest taki jak poprzedni, a jeżeli nie to dodajesz go do tej drugiej tablicy która nie ma duplikatów (tworzysz ją przed wejściem do pętli).

Drugi sposób to taki jak napisałeś z tym, że nie potrzebujesz licznika nawet tylko zwykłego booleana. Przed wejściem do wewnętrznej pętli ustawiasz go na true i jeżeli w wewnętrznej pętli przy porównywaniu obu elementów okaże się, że znalazłeś duplikat to ustawiasz go na false. Jeżeli po wyjściu z wewnętrznej pętli ten boolean dalej jest ustawiony na true to dodajesz element do tablicy wynikowej, którą utworzyłeś na samym początku.

---

@Tomasz90, a co Cię to wtedy nauczy ? Jaki to jest sens, po drugie " wiesz co się dzieje pod spodem" ile operacji jest wykonywanych, jakie to jest marnowanie zasobu pamięci, czasu algorytmicznego etc?... właśnie to jest to - jak ktoś nie myśli :) tylko używa czegoś " bo to coś tak działą, więc użyjmy tego do tego celu " 

---

Nigdzie nie było napisane czy w tym zadaniu on może używać kolekcji czy nie (w momencie gdy udzielałem odpowiedzi). Nie wiem na jakim poziomie osoba pytająca zna Jave, to udzieliłem takiej odpowiedzi. Jak autor napisał, że nie może to opisałem mu słownie algorytm bez ich użycia. Śmieszy mnie, że mądrzysz się w każdym temacie, masz każdego za głupka tak jakby implementacja zbioru, listy, haszmapy była jakąś wiedzą tajemną, którą jedynie Ty na tym forum posiadasz.

---

@Wiciorny, hmm.. nie wiem... to co napisałeś o "sensie i dzianiu się pod spodem" to argumentacja czy manifestacja przekonań? :) Bo jeśli to 1 to mam inne zdanie a jeśli to 2 to nie ma sensu ich zmieniać jeśli Ci się sprawdzają.