Hoe bepaal je of een bepaald woord tussen twee andere woorden komt?

Laten we voor de eenvoud zeggen dat ik twee sets woorden heb, gesorteerd in alfabetische volgorde. Eén set begint bij "aardvarken" en eindigt bij "meloen", en de andere begint bij "meloen" en eindigt bij "zebra". Het woord "meloen" verschijnt in beide sets.

Als ik een invoerwoord zou nemen, zeg 'banaan', wat zou dan een goede (en efficiënte) manier zijn om te bepalen tot welke woordenreeks het zou behoren? Opmerking: dit is geen vraag over het feit of het woord 'banaan' al in één set bestaat, maar eerder een vraag over hoe je kunt bepalen in welke set het woord hoort .

Als er een algoritme is dat iemand kent, geweldig. Als ze een versie in Java kunnen leveren, nog beter!

Bewerken: moet ook wijzen op, terwijl mijn voorbeeld slechts 2 sets heeft, wil ik dat het algoritme met n sets werkt.

2
@GarrettHall - Nee, op basis van alfabetische volgorde.
toegevoegd de auteur Rsaesha, de bron
@birryree - Ja, meloen is altijd het laatste woord. Ik heb echter maar 2 sets voor de eenvoud. Ik wil een algoritme kennen voor n aantal sets.
toegevoegd de auteur Rsaesha, de bron
Is in uw voorbeeld "meloen" (of welk woord dan ook) altijd het laatste item in de eerste reeks? Als dit het geval is, is dit net zo eenvoudig als controleren of het woord w vóór het laatste item van de eerste set komt (dit is "melon" in uw geval). Ervan uitgaande dat u bedoelt in gesorteerde volgorde. Gegeneraliseerd, u hoeft alleen elke set te controleren om te zien of dat woord vóór het laatste item in de set komt en vervolgens te bepalen of het vóór of na het eerste item staat. Als het niet eerder komt, hoort het thuis in die set.
toegevoegd de auteur wkl, de bron
zou moeten bestaan ​​op basis van wat? categorie?
toegevoegd de auteur Garrett Hall, de bron

6 antwoord

Stel dat u sets van n heeft. Construeer een lijst met de woorden "partitie" in gesorteerde volgorde.

Dan is de set waar hij toe behoort simpelweg:

List partitions = Arrays.asList("melon", "strawberry");
int setIndex = -(Collections.binarySearch(partitions, "banana")) - 1;

Dit werkt omdat Collections.binarySearch retourneert de invoegpositie (-1) als deze de sleutel niet in de lijst kan vinden. Als het kan botsen met een van de partitiewoorden, moet u eerst controleren of het resultaat negatief is.

Bewerk

I Bewerked to remove the requirement for the "book-end" values ("aardvark" and "zebra") as they actually only complicated things.

2
toegevoegd

Voor twee sets:

Als woord uw woord is (bijvoorbeeld "banana" ):

int cmp = word.compareTo("melon");
if (cmp < 0) {
 //it belongs to the first set
} else if (cmp > 0) {
 //it belongs to the second set
} else {
 //the word is "melon"
}

Voor n sets:

Place the dividing words into an ArrayList (call it dividers) in alphabetical order:

ArrayList dividers = new ArrayList();
//... populate `dividers` ...
Collections.sort(dividers);

Nu kunt u Collections.binarySearch() gebruiken om uit te zoeken tot welke set het woord behoort:

int pos = Collections.binarySearch(dividers, word);
if (pos >= 0) {
 //the word is the divider between sets `pos` and `pos+1`
} else {
  int num = -(pos + 1);
 //the word belong to set number `num`
}

(Hier zijn de sets genummerd vanaf nul.)

2
toegevoegd
Ok, maar wat als er meer dan 2 sets zijn? Sorry, vergat dit aan de oorspronkelijke vraag toe te voegen. Ik heb maar 2 sets gebruikt voor de eenvoud, maar mijn eigenlijke programma heeft veel sets, allemaal alfabetisch gesorteerd. Dus bijvoorbeeld: aardvarken - appel, appel - banaan, banaan - misdaad, misdaad - hond, ... enz
toegevoegd de auteur Rsaesha, de bron
@birryree - Als deze gelijk is aan het laatste woord in de set, moeten zowel die set als de set after (indien aanwezig) worden geretourneerd.
toegevoegd de auteur Rsaesha, de bron
@Rsaesha - wat gebeurt er wanneer het woord gelijk is aan het laatste woord in de set?
toegevoegd de auteur wkl, de bron
String mid = firstList.get(firstList.size()-1);
assert(mid.equals(secondList.get(0)));
if(newString.compareTo(mid) < 0)//belongs in first
else//belongs in second.

Het is duidelijk dat je sommige van de methodeaanroepen mogelijk moet aanpassen, afhankelijk van hoe je ze vasthoudt.

0
toegevoegd
    final int n = 99;//whatever

    final SortedSet[] allMySets = new SortedSet[ n ];

   //put your sets into allMySets, no particular order required.

    final String searchWord = "banana";

    int i;

    for ( i = 0; i < allMySets.length; i++ ) {

        final SortedSet< String > ss = allMySets[i];

        if ( searchWord.compareTo( ss.first() ) >= 0 && searchWord.compareTo( ss.last() ) <= 0 ) {
            System.out.println("Word " + searchWord + " belongs to set #" + i);
            break;
        }

    }

    if ( i == allMySets.length ) {
        System.out.println("No matching set found.");
       //Maybe handle border case here...
    }
0
toegevoegd

Als u een binaire heap gebruikt om de lijsten op te slaan, bepaalt u waar u een woord moet invoegen O ( log n)

0
toegevoegd

Controleer de eerste letter en kijk of deze tussen (eerste letter van set 1) en (eerste letter van laatste element van set 1) staat. Als het gelijk is aan beide eerste letters, ga dan verder met de tweede letters. Als het niet in die set past, ga dan naar de volgende set. Dit is BigO (n * m), waarbij n het aantal sets is en m het aantal letters in uw invoerwoord is. Niet zo erg IMO.

0
toegevoegd