java - 确定 Java 中的等效数组

Question

在java中，判断两个数组是否包含所有相同元素的最有效方法是什么。数组可以有重复项，也可以未排序。最高效意味着运行时间复杂度和空间复杂度。

Answer 1

您也可以使用 HashMap 来跟踪您之前看到的值:

public static void main(String[] args) {
    System.out.println(allEquivalents(new String[][] { { "1", "3" }, { "1", "1", "3" } })); // true
    System.out.println(allEquivalents(new String[][] { { "1" }, { "1", "1", "1" }, { "1", "1", "2" } })); // false
}

public static boolean allEquivalents(String[][] arrays) {
    final HashMap<String, Integer> foundValues = new HashMap<String, Integer>();
    for (int i = 0; i < arrays.length; i++) {
        for (final String key : arrays[i]) {
            // we have a value not seen in the previous array, return false
            if (i > 0 && (!foundValues.containsKey(key) || foundValues.get(key) < i - 1)) {
                return false;
            }
            foundValues.put(key, i);
        }
    }
    // check if all the values where in the last array
    for (final Integer i : foundValues.values()) {
        if (i < arrays.length - 1) {
            return false;
        }
    }
    return true;
}

您仅对每个值以及 HashMap 中的值迭代一次。因此，复杂度为 O(n)，值总数为 n。