Як вызначыць, ці ідзе дадзенае слова паміж двума іншымі словамі?

Для прастаты дапусцім, што ў мяне ёсць два набору слоў, адсартаваных ў алфавітным парадку. Адзін набор пачынаецца з «мурашкаед» і заканчваецца на «дыня», а другі пачынаецца на «дыня» і заканчваецца на «зебры». Слова «дыня» з'яўляецца ў абодвух наборах.

Калі б я ўзяць уваходнае слова, скажам, «банан», што было б добра (і эфектыўны) спосаб вызначэння, які набор слоў ён павінен належаць? Заўвага: гэта не пытанне аб тым, ці існуе ўжо слова «банан» у адным наборы, а хутчэй пытанне аб тым, як вызначыць, які набор слова павінен існуе.

Калі ёсць алгарытм, які хтосьці ведае, выдатна. Калі яны могуць забяспечыць некаторую версію ў Java, нават лепш!

Edit: Варта таксама сказаць пра, у той час як мой прыклад мае толькі 2 камплекты, я хачу, каб алгарытм працы з п мностваў.

2
@GarrettHall - Не, заснаваны на алфавітным парадку.
дададзена аўтар Rsaesha, крыніца
@birryree - Так, дыня заўсёды апошняе слова. Тым не менш, у мяне ёсць толькі 2 камплекты для прастаты. Я хачу ведаць алгарытм п колькасці мностваў.
дададзена аўтар Rsaesha, крыніца
У вашым прыкладзе, гэта «дыня» (ці што-то слово) заўсёды апошні элемент у першым сэце? Калі так, то гэта так жа проста, як правяраць, калі слова ж ідзе да апошняга пункта першага набору (які «дыня» у вашым выпадку). Мяркуючы, што вы маеце на ўвазе ў адсартаваным парадку. Абагульнены, вы проста павінны праверыць кожны набор, каб убачыць, калі гэта слова паходзіць да апошняга элемента ў наборы, а затым вызначыць, ці з'яўляецца гэта да або пасля першага пункта. Калі ён не прыходзіць раней, яна належыць ў гэтым наборы.
дададзена аўтар wkl, крыніца
павінны існаваць у аснове на што? катэгорыя?
дададзена аўтар Garrett Hall, крыніца

6 адказы

Скажам, у вас ёсць п наборы. Пабудаваць спіс «раздзелы» словы ў адсартаваным парадку.

Тады мноства належыць проста:

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

Гэта працуе, таму што Collections.binarySearch вяртае пазіцыю ўстаўкі (-1), калі ён не можа знайсці ключ у спісе. Калі ён можа сутыкнуцца з адным з раздзелаў слоў, то вы павінны спачатку праверыць, ці з'яўляецца вынік адмоўны.

рэдагаваць

I рэдагавацьed to remove the requirement for the "book-end" values ("aardvark" and "zebra") as they actually only complicated things.

2
дададзена

<�Моцны> Для двух мностваў:

Калі слова Ваша слова (напрыклад, "банан" ):

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"
}

Для N наборы:

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

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

Цяпер вы можаце выкарыстоўваць Collections.binarySearch() , каб высветліць, які набор слова належыць:

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`
}

(Тут, наборы пранумараваны ад нуля.)

2
дададзена
Добра, але што, калі ёсць больш чым 2 камплекты? На жаль, забыўся дадаць, што да першапачатковага пытанні. Я толькі выкарыстаў 2 набору для прастаты, але мая бягучая праграма будзе мець шмат набораў, усё ў алфавітным парадку. Так, напрыклад: мурашкаеда - яблык, яблык - банан, банан - злачынства, злачынства - сабака, ... і г.д.
дададзена аўтар Rsaesha, крыніца
@birryree - Калі ён роўны апошнім слове ў наборы, то як гэты набор, і набор пасля (калі ён існуе) павінен быць вернуты.
дададзена аўтар Rsaesha, крыніца
@Rsaesha - тое, што адбываецца, калі слова роўна апошняе слова ў наборы?
дададзена аўтар wkl, крыніца
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.

Відавочна, што вам, магчыма, прыйдзецца адаптаваць некаторыя з выклікаў метадаў у залежнасці ад таго, як вы трымаеце іх.

0
дададзена
    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
дададзена

Калі вы карыстаецеся для захоўвання спісаў, то вызначыць, дзе ўставіць слова будзе прымаць O ( § п)

0
дададзена

Проста праверце першую літару і паглядзець, калі гэта паміж (першай літарай набору 1) і (першай літарай апошняга элементам набору 1). Калі ён роўны як першыя літары, пяройдзем да другой літары. Калі ён не падыходзіць у гэтым мностве пераходу да наступнага набору. Гэта BIGO (п * м), дзе п лік мностваў і т ёсць лік літар у вашым ўваходным слове. Не так ужо дрэнна IMO.

0
дададзена