唯一地标识顺序无关紧要的数字数组 [英] Uniquely identify an array of numbers whose order doesn't matter

问题描述

假设我有以下3个整数数组：

Let's say I have these 3 integer arrays:

int[] a = {1, 2, 3};
int[] b = {3, 4, 5};
int[] c = (2, 1, 3};

我在寻找对于最有效的代码，它将考虑与c相同（因为它们包含相同的数字，但顺序不同），但考虑与b不同，并且b与c不同。

I'm looking for the most efficient code that will consider a the same as c (because they contain the same numbers but in a different order), but consider a different from b, and b different from c.

我知道我可以对它们进行排序，使c变成{1、2、3}，因此与a相同，但是我正在比较数百个数组，每个数组都有三个以上的数字，我不想我的程序对它们中的每一个进行排序，我认为必须有一种更好的方法。

I know I can sort them all so that c becomes {1, 2, 3} and therefore the same as a, but I'm comparing hundreds of arrays with more than three numbers each and I don't want my program to sort each one of them, I'm thinking there must be a better way.

另外，例如，将总和作为是无效的，因为{1、4、5}中的数字之和与{1、3、6}中的数字之和。

Also, taking the sum, for example, wouldn't work because the sum of numbers in {1, 4, 5} is the same as that of numbers in {1, 3, 6}.

该乘积也不起作用因为{1、2、6}中数字的乘积与{1、3、4}中数字的乘积相同。

And the product wouldn't work either because the product of numbers in {1, 2, 6} is the same as that of numbers in {1, 3, 4}.

推荐答案

排序是一个O（nlog（n）操作（在最坏的情况下）。相反，您可以通过在两个数组上运行并只运行O（n）解决方案计算其中的元素：

Sorting is an O(nlog(n) operation (in the worst case). You could, instead, have an O(n) solution by running over both arrays and just counting the elements in it:

public static boolean hasSameElements(int[] a, int[] b) {
    return countElements(a).equals(countElements(b);)
}

private static Map<Integer, Long> countElements(int[] arr) {
    return Arrays.stream(arr)
                 .boxed()
                 .collect(Collectors.groupingBy(Function.identity(), 
                          Collectors.counting()));
}

编辑：

虽然它不会改变该算法的big-O表示法，通过快速失败，稍微不那么优雅的解决方案对于不匹配的数组可能会表现更好：

While it won't change the big-O notation of the algorithm, a slightly less elegant solution could perform better for non-matching arrays by failing fast:

public static boolean hasSameElements(int[] a, int[] b) {
    if (a.length != b.length) {
        return false;
    }

    Map<Integer, Long> popCount =
            Arrays.stream(a)
                  .mapToObj(Integer::valueOf)
                  .collect(Collectors.groupingBy(Function.identity(), 
                           Collectors.counting()));

    for (int elem : b) {
        Long count = popCount.get(elem);
        if (count == null) {
            return false;
        }
        count--;
        if (count == 0L) {
            popCount.remove(elem);
        } else {
            popCount.put(elem, count);
        }
    }

    return popCount.isEmpty();
}

这篇关于唯一地标识顺序无关紧要的数字数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！