与排序集混淆 Java

Question

我已经为用户定义的 class 实现了一个排序集，并且还使用 Comparable 接口为用户定义的 class 实现了 compareTo 方法。现在我的要求是，如果一个字符（即 a 到 z）已经存在，则增加字符的频率，否则根据它们的频率对输入进行排序。

String s = "abc"; // or "aaaab"  or any set of string between [ a - z ]
SortedSet<FreequencyIndex> sortedSet = new TreeSet<FreequencyIndex>();
    FreequencyIndex  symbol;
    for(int index = s.length() - 1; index >=0 ; index--){                            
        symbol = new FreequencyIndex(s.charAt(index), index, 0);            
        sortedSet.add(symbol);            
    }

System.out.println(sortedSet);

用户定义class：

 class FreequencyIndex implements Comparable<FreequencyIndex>{
    char symbol;
    int index;
    int frequency;

    public FreequencyIndex(char newSymbol, int newIndex, int newFrequency){
        this.symbol = newSymbol;
        this.index = newIndex;
        this.frequency = newFrequency;
    }

    @Override
    public String toString(){
        return this.symbol + " "+ this.frequency;
    }

    @Override
    public int compareTo(FreequencyIndex f2){            
        if(this.symbol == f2.symbol){       
            f2.frequency++;
            return 0;
        }
        else            
        if(this.frequency > f2.frequency)
            return 1;
        else            
            return -1;  


    }
}

对于输入 S = "a" -> 排序集将是 [a 0] 但它给出 [a, 1]
对于输入 S = "ab" -> 排序集将是 [a 0, b 0] 但它给出 [a 0, b 1]
对于输入 S = "aba" -> 排序集将是 [ b 0, a 2] 但它给出 [b 0, a 2]
对于输入 S = "aab" -> 排序集将是 [ b 0, a 2] 但它给出 [a 1, b 1]

我在这里遗漏了什么，有人可以解释一下吗？

Answer 1

一个SortedSet是一个有某种排序的集合，最臭名昭著的是TreeSet。但是，排序对于在调用 add 时找出节点是否已经存在也很重要。因此，您按与符号不同的东西排序的解决方案会破坏它。

此外，当您向任何类型的集合添加内容时，无论是 TreeSet、HashSet 还是几乎任何其他集合，您都不应该修改该对象，或者至少，它的字段用于比较。这意味着，如果您以某种方式更改对象，equals、compareTo 或 hashCode 等方法仍应 return 相同的值，否则您的设置将无法正常工作，并且它甚至会导致重复出现。

在您的情况下，最干净的解决方案是不使用 FrequencyIndex 作为任何内容的键，而使用 Map<Character, FrequencyIndex> 按符号进行搜索。除非您在添加新元素的过程中多次需要排序集，否则您可以在完成频率检查后对其进行排序，下面的代码可以使用 Java 8 流很容易地使用上述地图完成：

map.values().stream()
    .sorted(Comparator.comparing(FrequencyIndex::getFrequency))
    .collect(Collectors.toList());

提到的 getter 频率 - 我认为您应该将 getters 添加到 FrequencyIndex class.

Efficiency 实际上可能会更好 - 在频率检查期间没有重新排序，并且只在与输入大小相比相当小的集合上完成一次。

与排序集混淆 Java

Confusion with Sorted Set Java

java

collections

sortedset