de-vraag
さらに
質問

与えられた単語が他の2つの単語の間に来るかどうかを判断する方法は？

簡単にするために、私はアルファベット順にソートされた2組の単語を持っているとしましょう。 1セットは "aardvark"で始まり "melon"で終わり、もう1セットは "melon"で始まり "zebra"で終わります。 「メロン」という言葉が両方のセットに現れます。

「バナナ」という言葉を入力すると、どの単語が属するべきかを判断するうえで、効果的な方法は何でしょうか？注：これは「バナナ」という単語がすでに1セットに存在するかどうかについての質問ではなく、 という単語がどのセットに存在すべきかを判断する方法に関する質問です。

誰かが知っているアルゴリズムがあれば、素晴らしい。彼らはJavaでいくつかのバージョンを提供することができれば、さらに良い！

編集：私の例は2セットしか持っていませんが、私はアルゴリズムがn個のセットで動作するようにしたいのですが、指摘すべきです。

Rsaesha
Rsaesha
編集された質問 27日 10月 2011 в 7:07
プログラミング
java

2つのセットの場合：

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 セットの場合：

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

（ここでは、セットは0から番号が付けられています）。

n セットがあるとします。ソートされた順序で「パーティション」単語のリストを作成します。

それが属しているセットは単にです：

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

これは、 Collections.binarySearch は、リスト内でキーが見つからない場合は挿入位置（-1）を返します。パーティションワードの1つと衝突する可能性がある場合は、最初に結果が否定的であるかどうかを確認する必要があります。

編集

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

最初の文字をチェックして、それが（1の最初の文字）と（1の最後の要素の最初の文字）の間にあるかどうかを確認します。両方の最初の文字に等しい場合は、2番目の文字に移動します。そのセットに収まらない場合は、次のセットに移動します。これはBigO（n * m）です。ここで、nは集合の数であり、mは入力単語の文字数です。あまりにも悪いIMO。

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（ログn）

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