Uklanjanje ponavljanih znakova iz niza

1. Pregled

U ovom uputstvu razmotrit ćemo nekoliko tehnika na Javi o uklanjanju ponovljenih znakova iz niza.

Za svaku tehniku, ukratko ćemo razgovarati i o njegovoj vremenskoj i prostornoj složenosti.

2. Korištenje različit

Počnimo s uklanjanjem duplikata iz našeg niza pomoću različit metoda uvedena u Javi 8.

U nastavku donosimo primjerak IntStream iz datog objekta niza. Zatim koristimo različit metoda za uklanjanje duplikata. Napokon, zovemo za svakoga metoda za prelazak preko različitih znakova i dodavanje ih našem StringBuilder:

StringBuilder sb = novi StringBuilder (); str.chars (). distinct (). forEach (c -> sb.append ((char) c));

Složenost vremena: Na) - vrijeme izvođenja petlje izravno je proporcionalno veličini ulaznog niza

Pomoćni prostor:Na) - budući da različit koristi a LinkedHashSet interno, a rezultirajući niz također pohranjujemo u StringBuilder objekt

Održava red: Da - od LinkedHashSet održava redoslijed svojih elemenata

I, iako je lijepo što Java 8 tako lijepo radi ovaj zadatak za nas, usporedimo ga s naporima da pokrenemo svoje.

3. Korištenje indexOf

Naivni pristup uklanjanju duplikata iz niza jednostavno uključuje petljajući po ulazu i koristeći indexOf metoda za provjeru postoji li trenutni znak već u rezultirajućem nizu:

StringBuilder sb = novi StringBuilder (); int idx; for (int i = 0; i <str.length (); i ++) {char c = str.charAt (i); idx = str.indexOf (c, i + 1); if (idx == -1) {sb.append (c); }} 

Složenost vremena: O (n * n) - za svaki znak, indexOf metoda prolazi kroz preostali niz

Pomoćni prostor:Na) - potreban je linearni prostor jer koristimo StringBuilder za pohranu rezultata

Održava red: Da

Ova metoda ima istu složenost prostora kao i prvi pristup, ali izvodi mnogo sporije.

4. Korištenje niza znakova

Također možemo ukloniti duplikate iz svog niza do pretvarajući ga u ugljen niz, a zatim petljajući svaki znak i uspoređujući ga sa svim sljedećim znakovima.

Kao što možemo vidjeti u nastavku, stvaramo dvije za petlje i provjeravamo ponavlja li se svaki element u nizu. Ako se pronađe duplikat, ne dodajemo ga na StringBuilder:

char [] znakovi = str.toCharArray (); StringBuilder sb = novi StringBuilder (); logička ponavljaChar; for (int i = 0; i <chars.length; i ++) {repeatChar = false; for (int j = i + 1; j <chars.length; j ++) {if (chars [i] == chars [j]) {repeatChar = true; pauza; }} if (! repeatChar) {sb.append (chars [i]); }} 

Složenost vremena: O (n * n) - imamo unutarnju i vanjsku petlju koje obilaze ulazni niz

Pomoćni prostor:Na) - potreban je linearni prostor od znakovi varijabla pohranjuje novu kopiju unosa niza, a mi također koristimo StringBuilder za spremanje rezultata

Održava red: Da

Ponovno, naš drugi pokušaj ima lošu izvedbu u usporedbi s Core Java ponudom, ali da vidimo gdje ćemo doći sa svojim sljedećim pokušajem.

5. Korištenje sortiranja

Alternativno, ponovljeni znakovi mogu se eliminirati sortiranjem našeg ulaznog niza u grupiranje duplikata. Da bismo to učinili, moramo pretvoriti niz u char array i sortirajte ga pomoću Nizovi.vrsta metoda. Konačno, ponovit ćemo sortirano ugljen niz.

Tijekom svake iteracije uspoređivat ćemo svaki element niza s prethodnim elementom. Ako su elementi različiti, tada ćemo dodati trenutni znak na StringBuilder:

StringBuilder sb = novi StringBuilder (); if (! str.isEmpty ()) {char [] znakovi = str.toCharArray (); Nizovi.sort (znakovi); sb.append (znakovi [0]); for (int i = 1; i <znakovi.duljina; i ++) {if (znakovi [i]! = znakovi [i - 1]) {sb.append (znakovi [i]); }}}

Složenost vremena: O (n zapisnik n) - sorta koristi dvostruki pivot Quicksort koji nudi O (n log n) izvedbu na mnogim skupovima podataka

Pomoćni prostor:Na) - od toCharArray metoda pravi kopiju ulaznih podataka Niz

Održava red: Ne

Pokušajmo to ponovno s našim posljednjim pokušajem.

6. Korištenje a Postavi

Drugi način uklanjanja ponovljenih znakova iz niza je upotreba a Postavi. Ako nas nije briga za redoslijed znakova u našem izlaznom nizu, možemo koristiti a HashSet.Inače možemo koristiti a LinkedHashSet kako bi se održao redoslijed umetanja.

U oba ćemo slučaja prelaziti preko ulaznog niza i dodati svaki znak u Postavi. Jednom kad se znakovi umetnu u skup, ponovit ćemo ga kako bismo ih dodali u StringBuilder i vratite rezultirajući niz:

StringBuilder sb = novi StringBuilder (); Postavi linkedHashSet = novi LinkedHashSet (); za (int i = 0; i <str.length (); i ++) {linkedHashSet.add (str.charAt (i)); } za (Znak c: linkedHashSet) {sb.append (c); } 

Složenost vremena: Na) - vrijeme izvođenja petlje izravno je proporcionalno veličini ulaznog niza

Pomoćni prostor:Na) - prostor potreban za Postavi ovisi o veličini ulaznog niza; također koristimo StringBuilder za pohranu rezultata

Održava red:LinkedHashSet - Da, HashSet - Ne

A sada smo se uskladili s pristupom Core Java! Nije baš šokantno saznati da je ovo vrlo slično onome različit već čini.

7. Zaključak

U ovom smo članku opisali nekoliko načina uklanjanja ponovljenih znakova iz niza u Javi. Također smo proučili složenost vremena i prostora svake od ovih metoda.

Kao i uvijek, isječke koda možete pronaći na GitHubu.