Блог

Для простоты предположим, что у меня есть два набора слов, отсортированных в алфавитном порядке. Один набор начинается с «aardvark» и заканчивается на «melon», а другой начинается с «melon» и заканчивается на «zebra». Слово «дыня» появляется в обоих наборах.

Если бы я взял входное слово, скажем, «банан», что было бы хорошим (и эффективным) способом определить, к какому набору слов оно должно принадлежать? Примечание: это не вопрос о том, существует ли слово «банан» уже в одном наборе, а скорее вопрос о том, как определить, в каком наборе должно существовать слово.

Если есть алгоритм, который кто-то знает, отлично. Если они могут предоставить некоторую версию на Java, еще лучше!

Редактировать: следует также указать, что, хотя в моем примере всего 2 набора, я хочу, чтобы алгоритм работал с n наборами.

Для двух наборов:

Если word это ваше слово (например "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 наборов:

Поместите разделительные слова в ArrayList<String> (назовите это dividers ) в алфавитном порядке:

 ArrayList<String> dividers = new ArrayList<String>();
//... 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`
}
 

(Здесь наборы нумеруются с нуля.)

Допустим, у вас есть n наборы. Создайте список слов «раздела» в отсортированном порядке.

Тогда набор, к которому он принадлежит, просто:

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

Это работает, потому Collections.binarySearch что возвращает позицию вставки (-1), если он не может найти ключ в списке. Если оно может столкнуться с одним из слов раздела, вам следует сначала проверить, является ли результат отрицательным.

Редактировать

Я отредактировал, чтобы убрать требование для значений «book-end» («трубкозуб» и «зебра»), поскольку они на самом деле только усложняют ситуацию.

Просто проверьте первую букву и посмотрите, находится ли она между (первой буквой набора 1) и (первой буквой последнего элемента набора 1). Если оно равно обеим первым буквам, переходите ко вторым буквам. Если оно не вписывается в этот набор, перейдите к следующему набору. Это BigO(n * m), где n — количество наборов, а m — количество букв во входном слове. Не так уж плохо, ИМО.

 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.
 

Очевидно, вам может потребоваться адаптировать некоторые вызовы методов в зависимости от того, как вы их выполняете.

Если вы используете двоичную кучу для хранения списков, то определение того, куда вставить слово, займет O (log n).

     final int n = 99; // whatever

    final SortedSet<String>[] 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 amp;amp; 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...
    }