3

好的，所以我有一个程序，其中有一部分我需要“对单词进行排序，使得列表中每个项目的最后一个字母是下一个项目的第一个字母，一种由 last 和 first 链接在一起的单词链信。”

示例输入是 dog,elephant,giraffe,rhinoceros,tiger 正确的输出是 dog,giraffe,elephant,tiger,rhinoceros 而我的输出是tiger, rhinoceros, dog, giraffe,大象。

比较器是这样的：

class linkedSort implements Comparator {
    //will return 1 for a match
    //returns 0 if no match

    public int compare(Object t, Object t1) {
        char[] charArr1 = t.toString().toCharArray();
        char[] charArr2 = t1.toString().toCharArray();

        if (charArr1[charArr1.length - 1] == charArr2[0]) {
            return -1;
        } else {
            return 1;
        }
    }
}

任何帮助将不胜感激！！

4

4 回答 4

10

您无法使用简单的比较器和排序来解决此问题，因为比较没有定义总顺序。总订单是具有以下四个属性的订单：

  • 自反性：x ≤ x 总是正确的。
  • 反对称：如果 x ≤ y 且 x ≠ y，则 y ≤ x 永远不会成立。
  • 传递性：如果 x ≤ y 且 y ≤ z，则 x ≤ z
  • Totality：对于任何 x 和 y，x ≤ y 和 y ≤ x 中的至少一个成立。

您的订单不是总订单。首先，它打破了反身性：例如，“a”≤“a”。其次，它打破了反对称：“ease”≤“eve”和“eve”≤“ease”。第三，打破及物性：“east”≤“tea”，“tea”≤“aver”，但“east”≤“aver”为假。最后，不完全：“东”不小于“西”，“西”不小于“东”。

要解决此问题，您将需要以不同的方式处理它。作为提示，您可能希望将问题视为一个图形，其中字母是节点，单词是连接开始和结束字母的边。你能在这张图中找到一条对每条边都只访问一次的路径吗？

希望这可以帮助！

于 2012-02-15T21:51:19.393 回答
3

如果您希望使用 执行此操作sort，那么这将行不通。比较器需要对集合进行总排序，但您的要求不是这样的。

于 2012-02-15T21:51:30.047 回答
1

这相当于这个问题：Detecting when matrix multiplication is possible

  1. 为每个字母创建一个节点
  2. 将两个字母与相应动物的有向边连接起来（允许同一对顶点之间有多个边）
  3. 找到欧拉人的踪迹
于 2012-02-15T21:55:53.323 回答
0

该Comparator方法行不通。排序仅使用本地比较，但您的问题是全局“优化”问题。

为了说明，以下是来自 的实际比较Arrays.sort(array, comparator)。请注意，一些交换破坏了之前做出的正确选择，因为它们只有本地知识。

start: dog,elephant,giraffe,rhinoceros,tiger

dog, elephant (swap)

-> elephant,dog,giraffe,rhinoceros,tiger

dog, giraffe (OK)

-> elephant,dog,giraffe,rhinoceros,tiger

giraffe, rhinoceros (swap)

-> elephant,dog,rhinoceros,giraffe,tiger

dog, rhinoceros (swap)

-> elephant,rhinoceros,dog,giraffe,tiger

elephant, rhinoceros (swap)

-> rhinoceros,elephant,dog,giraffe,tiger

giraffe, tiger (swap)

-> rhinoceros,elephant,dog,tiger,giraffe

dog, tiger (swap)

-> rhinoceros,elephant,tiger,dog,giraffe

elephant, tiger (OK)

-> rhinoceros, elephant, tiger, dog, giraffe
于 2012-02-15T21:53:32.030 回答