Verilen bir sözcüğün diğer iki kelime arasında mı geldiğini nasıl belirleyebilirim?

Basitlik için, alfabetik sıraya göre sıralanmış iki kelime grubumuz olduğunu varsayalım. Bir set "aardvark" ile başlar ve "kavun" ile biter, diğeri "kavun" da başlar ve "zebra" ile biter. Her iki kümede "kavun" kelimesi görünür.

Eğer bir giriş kelimesi alsaydım, "muz" deyin, hangi kelimelere ait olması gerektiğini belirlemenin iyi (ve etkili) yolu ne olurdu? Not: Bu, "banana" kelimesinin bir kümede zaten var olup olmadığı, ancak sözcüğünün kelimesinin hangi sette bulunacağını belirleme hakkında bir soru değildir.

Birinin bildiği bir algoritma varsa, harika. Java'da bazı sürümleri sağlayabilirlerse, daha da iyi!

Düzenleme: Ayrıca, örneklemin sadece 2 kümesine sahipken, algoritmanın n kümeleriyle çalışmasını istiyorum.

 2
katma düzenlendi
Görünümler: 25
kaynak
ro ru fr es pt de zh hi bn ar kk uz be uk
@GarrettHall - Hayır, alfabetik sıraya göre.
katma yazar Rsaesha, kaynak
@birryree - Evet, kavun her zaman son kelimedir. Ancak, sadelik için sadece 2 setim var. N sayıda set için bir algoritma bilmek istiyorum.
katma yazar Rsaesha, kaynak
Örneğinizde, "kavun" (veya herhangi bir kelime), her zaman ilk setteki son öğe nedir? Eğer öyleyse, bu, w kelimesinin ilk setin son öğesinden önce gelip gelmediğini kontrol etmek kadar basittir (sizin durumunuzda "kavun" ). Sıralı düzende demek istediğimi varsayarsak. Genelleştirilmiş olarak, her bir kümeyi, kümedeki son öğeden önce gelip gelmediğini görmek ve sonra ilk öğeden önce mi, sonra mı olduğunu belirlemek için kontrol etmeniz gerekir. Daha önce gelmezse, o sete aittir.
katma yazar wkl, kaynak
neye göre var olmalıdır? kategori?
katma yazar Garrett Hall, kaynak

6 cevap

Diyelim ki n kümeleriniz var. Sıralı düzende "bölüm" kelimelerinin bir listesini oluşturun.

Sonra ait olduğu set basitçe:

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

Bu, Collections.binarySearch , listede anahtarı bulamazsa ekleme konumunu (-1) döndürür. Eğer bölüm kelimelerinden biriyle çarpışırsa, önce sonucun negatif olup olmadığını kontrol etmelisiniz.

Düzenle

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

2
katma
kaynak

İki takım için:

kelimesi kelimenizse (ör. "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"
}

n için ayarlar:

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

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

Şimdi, sözcüğün hangi gruba ait olduğunu bulmak için Collections.binarySearch() 'ı kullanabilirsiniz:

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

(Burada setler sıfırdan numaralandırılmıştır.)

2
katma
kaynak
Tamam, ama ya 2'den fazla set varsa? Maalesef, bunu orijinal soruya eklemeyi unutma. Ben sadece basitlik için 2 set kullandım, fakat benim gerçek programımın hepsi alfabetik olarak sıralanmış çok sayıda kümeye sahip olacak. Örneğin: aardvark - elma, elma - muz, muz - suç, suç - köpek, ... vb
katma yazar Rsaesha, kaynak
@birryree - Eğer kümedeki son kelimeye eşitse, o zaman her ikisi de ayarlanır ve (eğer varsa) set geri gönderilmelidir.
katma yazar Rsaesha, kaynak
@Rsaesha - kelime sette son kelimeye eşit olduğunda ne olur?
katma yazar wkl, kaynak 
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.

Açıkçası, onları nasıl tuttuğunuza bağlı olarak bazı yöntem çağrılarını uyarlamanız gerekebilir.

0
katma
kaynak 
    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
katma
kaynak

Listeleri saklamak için bir ikili yığın kullanırsanız, bir kelimeyi nereye ekleyeceğinizi belirleme O ( log n)

0
katma
kaynak

Sadece ilk harfi kontrol edin ve aralarında (set 1'in ilk harfi) ve (set 1'in son elemanının ilk harfi) arasında olup olmadığına bakın. Her iki ilk harfe eşitse, ikinci harflere geçin. Bu sete uymuyorsa sonraki sete geçin. Bu, BigO (n * m) 'dir, burada n, set sayısıdır ve m, giriş kelimenizdeki harflerin sayısıdır. IMO değil çok kötü.

0
katma
kaynak