Bestem om alle elementene er de samme i en Java-liste

1. Oversikt

I denne raske opplæringen vil vi finne ut hvordan vi kan avgjøre om alle elementene i a Liste er det samme.

Vi vil også se på tidskompleksiteten til hver løsning ved hjelp av Big O-notasjon, noe som gir oss det verste tilfellet.

2. Eksempel

La oss anta at vi har følgende tre lister:

notAllEqualList = Arrays.asList ("Jack", "James", "Sam", "James"); emptyList = Arrays.asList (); allEqualList = Arrays.asList ("Jack", "Jack", "Jack", "Jack");

Vår oppgave er å foreslå forskjellige løsninger som kommer tilbake ekte bare for tomListe og allEqualList.

3. Grunnleggende looping

For det første er det sant at for at alle elementene skal være like, må de alle være like det første elementet. La oss dra nytte av det i en løkke:

public boolean verifyAllEqualUsingALoop (List list) {for (String s: list) {if (! s.equals (list.get (0))) return false; } returner sant; }

Dette er fint fordi, mens tidskompleksiteten er På), kan det ofte gå ut tidlig.

4. HashSet

Vi kan også bruke en HashSet siden alle elementene er forskjellige. Jegf vi konverterer a Liste til en HashSet og den resulterende størrelsen er mindre enn eller lik 1, så vet vi at alle elementene i listen er like:

public boolean verifyAllEqualUsingHashSet (List list) {return new HashSet (list) .size () <= 1; }

Konvertering av en Liste til HashSet kostnader På) tid mens du ringer størrelse tar O (1). Dermed har vi fortsatt en total tidskompleksitet på På).

5. Samlinger API

En annen løsning er å bruke frekvens (samling c, objekt o) metoden for Collections API. Denne metoden returnerer antall elementer i a Samling c matchende en Objekt o.

Så hvis frekvensresultatet er lik størrelsen på listen, vet vi at alle elementene er like:

public boolean verifyAllEqualUsingFrequency (List list) return list.isEmpty () 

I likhet med de tidligere løsningene er tidskompleksiteten På) siden internt, Collections. Frekvens () bruker grunnleggende looping.

6. Strømmer

De Strøm API i Java 8 gir oss enda flere alternative måter å oppdage om alle elementene i en liste er like.

6.1. distinkt()

La oss se på en bestemt løsning som bruker distinkt() metode.

For å kontrollere om alle elementene i en liste er like, vi teller de forskjellige elementene i strømmen:

public boolean verifyAllEqualUsingStream (List list) {return list.stream () .distinct () .count () <= 1; }

Hvis tellingen av denne strømmen er mindre eller lik 1, er alle elementene like, og vi kommer tilbake ekte.

Den totale kostnaden for operasjonen er På), det er tiden det tar å gå gjennom alle strømelementene.

6.2. allMatch ()

De Strøm API-er allMatch () metoden gir en perfekt løsning for å bestemme om alle elementene i denne strømmen samsvarer med det angitte predikatet:

public boolean verifyAllEqualAnotherUsingStream (List list) return list.isEmpty () 

I likhet med forrige eksempel ved bruk av strømmer, har denne en På) tidskompleksitet, som er tiden for å krysse hele strømmen.

7. Tredjepartsbiblioteker

Hvis vi sitter fast i en tidligere versjon av Java og ikke kan bruke Stream API, vi kan benytte oss av tredjepartsbiblioteker som Google Guava og Apache Commons.

Her har vi to løsninger som er veldig like, gjentar gjennom en liste over elementer og samsvarer med det første elementet. Dermed kan vi enkelt beregne tidskompleksiteten som skal være På).

7.1. Maven avhengigheter

For å bruke en av dem kan vi legge til en av dem guava eller felles-samlinger4 henholdsvis til prosjektet vårt:

 com.google.guava guava 23.0 
     org.apache.commons commons-collection4 4.1 

7.2. Google Guava

I Google Guava, den statiske metoden Iterables.all () returnerer ekte hvis alle elementene i listen tilfredsstiller predikatet:

public boolean verifyAllEqualUsingGuava (List list) {return Iterables.all (list, new Predicate () {public boolean apply (String s) {return s.equals (list.get (0));}}); }

7.3. Apache Commons

Tilsvarende Apache Commons biblioteket gir også en nytteklasse IterableUtils med et sett med statiske verktøy for bruk Iterabel tilfeller.

Spesielt den statiske metoden IterableUtils.matchesAll () returnerer ekte hvis alle elementene i listen tilfredsstiller predikatet:

public boolean verifyAllEqualUsingApacheCommon (List list) {return IterableUtils.matchesAll (list, new org.apache.commons.collections4.Predicate () {public boolean assess (String s) {return s.equals (list.get (0));} }); } 

8. Konklusjon

I denne artikkelen har vi lært forskjellige måter å verifisere om alle elementene i a Liste er like startende med enkel Java-funksjonalitet og deretter viser alternative måter å bruke Strøm API og tredjepartsbiblioteker Google Guava og Apache Commons.

Vi har også lært at hver av løsningene gir oss den samme tidskompleksiteten som På). Det er imidlertid opp til oss å velge den beste i henhold til hvordan og hvor den skal brukes.

Og sørg for å sjekke ut hele settet med eksempler på GitHub.


$config[zx-auto] not found$config[zx-overlay] not found