Lineæritmisk løsning?

[Denjam]

Formålet er å finne det første leksiografiske navnet som fremkommer i minst 3 av 4 fire lister.

 

Jeg har laget fire lister med dummy-navn. Deretter har jeg laget en superliste som tar alle navnene i alle listene, og sorterer ved java.util.Collections.sort(liste, Collator.getInstance());

 

Deretter går jeg bare gjennom denne listen og printer ut når noe fremkommer minst tre ganger etterhverandre.

 

Problemet: Jeg mistenker at Collections.sort ikke er lineæritmisk slik oppgavekravet er, og samtidig har denne løsningen et problem med duplikat i hver liste. Noen tips?

[Denjam]

Ok, jeg ser selv at jeg kan utføre en Merge Sort istedenfor, som er lineæritmisk. Men problemet med duplikater i hver liste vil finnes. Eksisterer det for eksempel tre Camillaer i første liste, så vil programmet finne at Camilla er felles for minst tre lister, men det er ikke nødvendigvis sant.

[Denjam]

Jeg har ombestemt meg litt. Per nå gjør programmet mitt dette:

 

1. Sorterer de fire listende i følge merge sort.

 

2. Legger de fire sorterte listene i fire forskjellige arrays.

 

3. Starter med å iterere gjennom elementene i første array, og gjør bit søk for å se om dette elementet

har en equals i en og en av de andre arraysene. Dersom ja, avslutter med print. Dersom nei:

 

4. Itererer gjennom elementene i andre array, og gjør bit søk for å se om dette elementet har en equals i en og en av de andre arraysene. Dersom ja, avslutter med print. Dersom nei, avslutter med print.

 

Gir dette mening ift. oppgavekravet om å lage en lineæritmisk metode for å finne det leksiografisk første elementet som finnes i minst tre av de fire listene?

Endret 21. oktober 2016 av Denjam