math - 我怎样才能简单地检查一组 n 数字是否都不同？

Question

我有 n 个整数，我需要一个快速的逻辑测试来查看它们是否都不同，而且我不想比较每个组合以找到匹配项......关于一个漂亮而优雅的方法的任何想法？

我不在乎你的想法是什么编程语言，我可以转换！

Answer 1

如果您的语言支持，请使用集合数据结构，您还可以考虑保留已看到元素的哈希表。

在python中你可以尝试

seen={}
n_already_seen=n in seen
seen[n]=n

n_already_seen将是一个布尔值，指示是否已经看到 n。

Answer 2

由于交换性和传递性，您不必检查每个组合；您可以简单地从列表中查看每个条目并对照它之后的每个条目检查每个条目。例如：

bool areElementsUnique( int[] arr ) {
    for( int i=0; i<arr.Length-1; i++ ) {
        for( int j=i+1; j<arr.Length; j++ ) {
            if( arr[i] == arr[j] ) return false;
        }
    }
    return true;
}

请注意，内部循环不是从头开始，而是从下一个元素 ( i+1) 开始。

Answer 3

您可以使用哈希表或使用哈希的 Set 类型的数据结构。然后，您可以将所有元素插入到哈希表或哈希集中，并在插入时检查元素是否已经在表/集中。如果由于某种原因您不想随时检查，您可以插入所有数字，然后检查结构的大小是否小于 n。如果它小于 n，则必须有重复的元素。否则，它们都是独一无二的。

这是一个非常紧凑的 Java 解决方案。时间复杂度摊销为 O(n)，空间复杂度也为 O(n)。

public boolean areAllElementsUnique(int [] list)
{
    Set<Integer> set = new HashSet<Integer>();
    for (int number: list)
        if (set.contains(number))
            return false;
        else
            set.add(number);
    return true;
}