如何确定给定的单词是否介于两个单词之间?

为简单起见,假设我有两组单词,按字母顺序排序。一组从“aardvark”开始,以“甜瓜”结束,另一组从“甜瓜”开始,以“斑马”结束。 “甜瓜”这个词出现在两组中。

如果我要输入一个输入词,比如说“香蕉”,那么确定它应该属于哪一组词的好(和有效)方法是什么?注意:这不是关于“香蕉”这个词是否已经存在于一个集合中的问题,而是一个关于如何确定单词应该存在于哪个集合的问题。

如果有人知道的算法,那很好。如果他们可以用Java提供一些版本,那就更好了!

编辑:也应该指出,虽然我的例子只有2套,我希望算法与n套一起使用。

2
@GarrettHall - 不,基于字母顺序。
额外 作者 Rsaesha,
@birryree - 是的,甜瓜永远是硬道理。但是,为简单起见,我只有2套。我想知道n个集合的算法。
额外 作者 Rsaesha,
在你的例子中,“melon”(或任何单词)总是第一组中的最后一项?如果是这样,这就像检查单词 w 是否在第一组的最后一项(在你的情况下是“melon”)之前一样简单。假设你的意思是排序顺序。广义输出,您只需要检查每个集合以查看该单词是否出现在集合中的最后一个项目之前,然后确定它是在第一个项目之前还是之后。如果它不是之前,它属于那个集合。
额外 作者 wkl,
应该存在于什么基础上?类别?
额外 作者 Garrett Hall,

6 答案

假设你有 n 集。按排序顺序构造“分区”单词列表。

那么它所属的集合就是:

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
额外

两套:

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

(这里,集合从零开始编号。)

2
额外
好的,但如果有超过2套怎么办?对不起,忘了将其添加到原始问题中。为简单起见,我只使用了2套,但我的实际程序将有很多套,都按字母顺序排序。例如:aardvark - 苹果,苹果 - 香蕉,香蕉 - 犯罪,犯罪 - 狗,等等
额外 作者 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(记录n)

0
额外

只需检查第一个字母,看看它是否在(第1组的第一个字母)和(第1组的最后一个元素的第一个字母)之间。如果它等于两个首字母,则移到第二个字母。如果它不适合该组移动到下一组。这是BigO(n * m),其中n是集合的数量,m是输入单词中的字母数。 IMO还不错。

0
额外