streamalism.org

1. Prehľad

V tomto výučbe si ukážeme niekoľko techník v Jave, ako odstrániť opakované znaky z reťazca.

Pre každú techniku tiež si v krátkosti povieme o časovej a priestorovej zložitosti.

2. Pomocou odlišný

Začnime odstránením duplikátov z nášho reťazca pomocou odlišný metóda zavedená v prostredí Java 8.

Ďalej získavame inštanciu súboru IntSvrhnúť sa z daného reťazcového objektu. Potom používame odlišný metóda na odstránenie duplikátov. Nakoniec voláme pre každý metóda na vytvorenie slučky cez odlišné znaky a ich pridanie k nášmu StringBuilder:

StringBuilder sb = nový StringBuilder (); str.chars (). zreteľný (). forEach (c -> sb.append ((char) c));

Časová zložitosť: O (n) - runtime cyklu je priamo úmerný veľkosti vstupného reťazca

Pomocný priestor:O (n) - od odlišný používa a LinkedHashSet interne a výsledný reťazec tiež ukladáme do a StringBuilder objekt

Udržuje objednávku: Áno - od LinkedHashSet udržuje poradie svojich prvkov

A hoci je pekné, že Java 8 túto úlohu za nás plní tak pekne, porovnajme ju so snahou zaviesť si svoju vlastnú.

3. Používanie indexOf

Naivný prístup k odstráneniu duplikátov z reťazca jednoducho zahŕňa slučka nad vstupom a použitie indexOf metóda na kontrolu, či aktuálny znak už vo výslednom reťazci existuje:

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

Časová zložitosť: O (n * n) - pre každú postavu, indexOf metóda prechádza zvyšným reťazcom

Pomocný priestor:O (n) - lineárny priestor je potrebný, pretože používame StringBuilder na uloženie výsledku

Udržuje objednávku: Áno

Táto metóda má rovnakú priestorovú zložitosť ako prvý prístup, ale vykonáva oveľa pomalšie.

4. Používanie poľa znakov

Môžeme tiež odstrániť duplikáty z nášho reťazca pomocou premenou na a char pole a potom zacykliť každý znak a porovnať ho so všetkými nasledujúcimi znakmi.

Ako vidíme ďalej, vytvárame dve pre slučky a kontrolujeme, či sa každý prvok v reťazci opakuje. Ak sa nájde duplikát, nepridávame ho k StringBuilder:

char [] chars = str.toCharArray (); StringBuilder sb = nový StringBuilder (); booleovský opakovanýChar; pre (int i = 0; i <chars.length; i ++) {opakovaneChar = false; for (int j = i + 1; j <chars.length; j ++) {if (chars [i] == chars [j]) {opakovaneChar = true; prestávka; }} if (! opakovaneChar) {sb.append (znaky [i]); }} 

Časová zložitosť: O (n * n) - máme vnútornú aj vonkajšiu slučku, ktoré prechádzajú vstupným reťazcom

Pomocný priestor:O (n) - je potrebný lineárny priestor, pretože znaky premenná ukladá novú kópiu vstupu reťazca a tiež používame StringBuilder pre uloženie výsledku

Udržuje objednávku: Áno

Náš druhý pokus má opäť slabú výkonnosť v porovnaní s ponukou Core Java, pozrime sa však, kam sa pri ďalšom pokuse dostaneme.

5. Používanie triedenia

Alternatívne je možné opakované znaky vylúčiť triedením nášho vstupného reťazca do skupinových duplikátov. Aby sme to mohli urobiť, musíme reťazec previesť na a char arozdrviť a roztriediť pomocou Polia.triediť metóda. Nakoniec prejdeme iteráciou zoradených char pole.

Počas každej iterácie budeme porovnávať každý prvok poľa s predchádzajúcim prvkom. Ak sú prvky odlišné, potom k znaku pripojíme aktuálny znak StringBuilder:

StringBuilder sb = nový StringBuilder (); if (! str.isEmpty ()) {char [] chars = str.toCharArray (); Array.sort (znaky); sb.append (znaky [0]); for (int i = 1; i <chars.length; i ++) {if (chars [i]! = chars [i - 1]) {sb.append (chars [i]); }}}

Časová zložitosť: O (n log n) - triedenie využíva dual-pivot Quicksort, ktorý ponúka O (n log n) výkon na mnohých množinách dát

Pomocný priestor:O (n) - od toCharArray metóda vytvorí kópiu vstupu String

Udržuje objednávku: Nie

Skúsme to ešte raz s našim posledným pokusom.

6. Pomocou a Nastaviť

Ďalším spôsobom, ako odstrániť opakované znaky z reťazca, je použitie a Nastaviť. Ak sa nestaráme o poradie znakov v našom výstupnom reťazci, môžeme použiť a HashSet.V opačnom prípade môžeme použiť a LinkedHashSet aby sa zachovala objednávka.

V obidvoch prípadoch urobíme slučku cez vstupný reťazec a každý znak pridáme do Nastaviť. Po vložení znakov do množiny ich budeme iterovať, aby sme ich mohli pridať do súboru StringBuilder a vráti výsledný reťazec:

StringBuilder sb = nový StringBuilder (); Nastaviť linkedHashSet = nový LinkedHashSet (); pre (int i = 0; i <str.length (); i ++) {linkedHashSet.add (str.charAt (i)); } pre (znak c: linkedHashSet) {sb.append (c); } 

Časová zložitosť: O (n) - runtime cyklu je priamo úmerný veľkosti vstupného reťazca

Pomocný priestor:O (n) - miesto potrebné na Nastaviť závisí od veľkosti vstupného reťazca; tiež používame StringBuilder na uloženie výsledku

Udržuje objednávku:LinkedHashSet - Áno, HashSet - Nie

A teraz sme dosiahli zhodu s prístupom Core Java! Nie je veľmi šokujúce zistiť, že je to veľmi podobné tomu, čo odlišný už áno.

7. Záver

V tomto článku sme sa venovali niekoľkým spôsobom, ako odstrániť opakované znaky z reťazca v Jave. Pozreli sme sa tiež na časovú a priestorovú zložitosť každej z týchto metód.

Útržky kódu ako vždy nájdete na GitHub.