Berilgan so'zlar boshqa ikki so'z o'rtasida bo'lsin-yo'qligini qanday aniqlash mumkin?

Oddiylik uchun, ikkita so'z birikmasi borligini aytaylik, alifbo tartibida tartiblangan. Bir qator "aardvark" da boshlanadi va "qovun" da tugaydi, ikkinchisi "qovun" dan boshlanadi va "zebra" da tugaydi. "Qovun" so'zi ikkala guruhda ham paydo bo'ladi.

Agar men kirish so'zini bersam, "banana" deb aytsa, qaysi so'z majmuasi unga tegishli bo'lishi kerakligini yaxshi (samarali) usul bilan qanday hal qilish mumkin? Eslatma: bu "banan" so'zi bitta to'plamda allaqachon mavjud bo'lganligi haqida emas, balki " so'zini qanday belgilash kerakligini aniqlash haqida savol. .

Agar kimdir biladigan algoritm bo'lsa, ajoyibdir. Agar Java-da ba'zi versiyalarni taqdim etsalar, yana yaxshi!

Tartibga solish: Shuni ta'kidlash kerakki, mening namunamda faqat 2 set mavjud bo'lsa, men algoritmni n-setlar bilan ishlashni xohlayman.

2
@GarrettHall - Yo'q, alfavit tartibida.
qo'shib qo'ydi muallif Rsaesha, manba
@birryree - Ha, qovun doimo oxirgi so'z. Ammo sodda bo'lish uchun faqat ikkita to'plam bor. Menga n to'plamlar soni uchun algoritmni bilishni istayman.
qo'shib qo'ydi muallif Rsaesha, manba
Sizning namunangizda "qovun" (yoki biron bir so'z) har doim birinchi to'siqdagi oxirgi elementmi? Agar shunday bo'lsa, bu w so'zining birinchi to'plamning oxirgi elementi (sizning holatingizda "qovun" ) dan oldin kelishini tekshirish uchun oddiy. Siz tartiblangan tartibda bo'lishingizni bilsangiz. Umumiy holda, siz har bir to'plamni ushbu so'zi to'plamdagi oxirgi elementdan oldin kelishini tekshirishingiz kerak va keyin u birinchi elementdan oldin yoki keyin bo'ladimi-yo'qligini aniqlang. Agar u ilgari kelmagan bo'lsa, u o'sha guruhga tegishli.
qo'shib qo'ydi muallif wkl, manba
nima asosida bo'lishi kerak? kategoriya?
qo'shib qo'ydi muallif Garrett Hall, manba

6 javoblar

Keling, sizda n sozlamalari mavjud. "Bo'lim" so'zining ro'yxatini tartiblangan tartibda tuzing.

Keyin u tegishli bo'lgan to'plam oddiy:

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

Buning sababi, Collections.binarySearch , ro'yxatda kalitni topa olmasa, qo'shish joyini (-1) qaytaradi. Bo'lim so'zlaridan biri bilan to'qnashsa, unda natijani salbiy yoki yo'qligini tekshirib ko'rishingiz kerak.

Tahrirlash

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

2
qo'shib qo'ydi

Ikki to'siq uchun:

so'z so'zingiz (masalan, "banana" ) bo'lsa:

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 uchun:

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

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

Endi Collections.binarySearch() dan foydalanishingiz mumkin.

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

(Bu erda, guruhlar noldan raqamlangan.)

2
qo'shib qo'ydi
OK, lekin agar ikkitadan ortiq to'siq bo'lsa? Kechirasiz, asl savolga qo'shib qo'yishni unutib qo'ydingiz. Men oddiylik uchun faqat 2 ta to'plamdan foydalanardim, lekin mening haqiqiy dasturim ko'plab to'plamlarga ega bo'ladi, ularning barchasi alifbo tartibida. Misol uchun: aardvark - olma, olma - banana, banana - jinoyat, jinoyat - it, va hokazo
qo'shib qo'ydi muallif Rsaesha, manba
@birryree - Agar ushbu to'plamdagi so'nggi so'zga teng bo'lsa, u holda ikkala set ham, keyin esa (agar mavjud bo'lsa) qaytarib berilishi kerak.
qo'shib qo'ydi muallif Rsaesha, manba
@Rsaesha - so'z majmuadagi so'nggi so'zga teng bo'lganda nima sodir bo'ladi?
qo'shib qo'ydi muallif wkl, manba
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.

Shubhasiz, ba'zi usullarni siz ularni qanday tutayotganingizga qarab moslashtirishingiz kerak bo'lishi mumkin.

0
qo'shib qo'ydi
    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
qo'shib qo'ydi

Agar siz ro'yxatlarni saqlash uchun o'zaro binafsha dan foydalansangiz, u holda so'zni qaerga qo'shishni belgilash O ( log n)

0
qo'shib qo'ydi

Faqat birinchi harfni tekshiring va u (1-gachaning birinchi harflari) va (1-sonning oxirgi elementining birinchi harflari) o'rtasida yoki yo'qligini bilib oling. Agar bu birinchi harfga teng bo'lsa, ikkinchi harfga o'ting. Agar u to'siqqa mos kelmasa, keyingi to'plamga o'tiladi. Bu BigO (n * m), bu erda n - to'siqlarning miqdori va m - kirish so'zingizdagi harflarning soni. IMO juda yomon emas.

0
qo'shib qo'ydi