检查所有给定的 n 个对象是否相同或不同的最有效方法？

Question

假设有两个字符串或任何对象，我想检查这两个对象是否相同，我会做 string1.equals(string2)，没问题。现在，如果有三个对象，我想看看它们是否都相等，我会做 string1.equals(string2) && string2.equals(string3) 并说四个，依此类推，这只有在给定参数大小的情况下才有可能。如果我将 n 个对象传递给方法，检查所有元素是否相等的最有效方法是什么。我写了

private static boolean equals(Object... objects) {
    Object obj = objects[0];
    boolean flag = false;
    for (Object object : objects) {
        if (object.equals(obj)) {
            flag = true;
        } else {
            flag = false;
            break;
        }
    }

    return flag;
}

但是当我向专业程序员展示这个时，他们指出这是一种非常低效的方法。如果我想检查所有元素是否都是唯一的，那将如何工作？是否有任何高效简洁的方法来检查任意 n 个元素是否相等或不同？

Answer 1

我真的不知道它是否更有效率，但是将所有值放入 Set 并比较数量的代码要少得多：

public static boolean areAllEqual(String ... words) {
    // put all the objects into a Set, which doesn't allow duplicates
    Set<String> setOfWords = new HashSet<>(Arrays.asList(words));

    // then compare the size of the Set to the length of the input array
    if (setOfWords.size() == words.length) {
        // and if those are equal, you have distinct values
        return true;
    } else {
        // otherwise there are at least two equal objects in the input array
        return false;
    }
}

我是这样查的：

public static void main(String[] args) {
    System.out.println(areAllEqual("equal", "equal", "equal", "equal", "equal", "equal", "equal"));
    System.out.println(areAllEqual("equal", "", "", "equal", "equal", "equal", "equal"));
    System.out.println(areAllEqual("equal", "", "", "", "", "", ""));
    System.out.println(areAllEqual("d", "i", "s", "t", "in", "ct", "values"));
}

产生输出

false
false
false
true

Answer 2

您可以尝试使用 Set 界面。如果您还不熟悉 Sets，请引用 Java documentation

A Set is a Collection that cannot contain duplicate elements. It models the mathematical set abstraction. The Set interface contains only methods inherited from Collection and adds the restriction that duplicate elements are prohibited. Set also adds a stronger contract on the behavior of the equals and hashCode operations, allowing Set instances to be compared meaningfully even if their implementation types differ. Two Set instances are equal if they contain the same elements.

由于 Set 不能包含重复元素，除非向其添加不同的元素，否则 Set 的大小将始终为一个，或者换句话说，Set 的大小永远不会等于传递的元素的大小除非它们都是独一无二的。在你的情况下它将是

private static boolean equals(Object... obj) {
   Set<Object> set = new HashSet<>(Arrays.asList(obj));
   return set.size() == 1; // Size of the Set should be one if all elements are same.
}

如果您要检查所有元素是否唯一，您可以检查 Set 的大小和传递的元素的大小是否相同。

Answer 3

您的实施实际上并没有那么低效。它做了一些多余的比较，但总的来说问题是线性的。无论实现如何，该算法都在 O(n) 之内，这意味着它是线性扩展的。（有关 O 表示法的详细信息，请参阅 https://en.wikipedia.org/wiki/Big_O_notation。

要证明数组中的所有元素都相等，您必须证明至少有一个元素彼此不相等。所以你正确地假设，第一次遇到不匹配就足以取消循环。您的实现的唯一问题是，您保留第一个元素，然后遍历所有元素（包括第一个），这比所需的多了 1 个比较。

然而，主要问题不是效率，而是null-安全。如果您的第一个对象是 null，您实际上调用了 null.equals...，它引发了 NullPointerException。相反，（可能）预期的行为是 return false.

因此：

private static boolean equals(Object... objects) {
    Object first = objects[0];
    if (first == null) {
         for (int i = 1; i < objects.length; ++i) {
             if (objects[i] != null) {
                 return false;
             }
         }
    } else {
        for (int i = 1; i < objects.length; ++i) {
            Object other = objects[i];
            if (other == null || !first.equals(other)) {
                return false;
            }
        }
    }
    return true;
}

检查所有给定的 n 个对象是否相同或不同的最有效方法？

Most efficient way to check if all given n objects are the same or distinct?

java

oop

loops

equals