检查一个数组是否是 2 个数组的合并

Question

实现一个函数，检查给定数组是否可以以任何方式构造为其他 2 个数组的合并。

public static boolean isMerge(int[] arr1, int[] arr2, int[] merge){
   //...
}

示例：

isMerge([3, 1, 2, 2], [2, 1, 1], [3, 1, 2, 2, 2, 1, 1]) -- true

isMerge([1, 2, 3], [4, 5, 6], [1, 2, 3, 4, 5, 6]) -- true

isMerge([1, 2, 3], [4, 5, 6], [1, 4, 5, 2, 3, 6]) -- true

isMerge([1, 2], [2, 3], [1, 2, 3, 2]) -- true

isMerge([1, 2], [3, 4], [1, 2, 3, 4, 5]) -- false

isMerge([1, 2], [3, 4], [1, 2, 5, 3, 4]) -- false

isMerge([1, 2], [3, 4], [5, 1, 2, 3, 4]) -- false

我的第一个想法是用 3 个迭代器实现一个解决方案。遍历每个数组检查 arr1 或 arr2 中的当前元素是否与 merge.

中的元素匹配

如果是，则继续迭代下一个元素，直到发现不匹配或证明 result 可以通过合并 arr1 和 arr2.

但解决方案在 isMerge([1, 2], [2, 3], [1, 2, 3, 2]) 上失败并报告 false。

我正在寻找在时间和内存方面最有效的解决方案，但有兴趣了解任何可行的方法。

Answer 1

这是我的做法。这是一种相对简单的方法，使用两个 Map 简单地计算两个数组（组合）和 merge 数组中值的出现次数。这可以在三个数组中最长的一个简单循环中完成。当然，只有当我们在合并数组中没有比在其他两个组合数组中更多的值时才会这样做。如果是这种情况，我们可以立即 return false 因为数组无法从两者合并。我也 return false 如果 merge 为空而其他两个数组中的任何一个都不是。

计算完值后，我们只需要比较两个映射的键和值。如果所有键及其各自的值都匹配，则可以通过合并两者来创建数组。

运行时是 O(n)，在 n 上有两个循环，所以大致 2n + k 其中 n 是提供的最大数组中的元素数，k 是一个小常量（取决于你如何计算一个操作），用于除函数中发生的循环之外的所有操作。

在内存方面，我们有 a、b、n 的长度 arr1、arr2、merge（它们中的任何一个都可以具有任何长度，但对于此计算，我们假设 a = arr1.length、b = arr2.length 和 n = merge.length）。然后我们有两个地图的内存要求：

对于 merge：(n * 0.75 + 1)*2
对于 arr1 和 arr2：((a + b) * 0.75 + 1)*2

下一个 2 的幂将由 Java 在内部用于数组的容量，因此在最坏的情况下，我们需要双倍的 space 数量然后实际需要存储值，因此*2.

参见 Java HashMap 中确定后备数组大小的代码：

/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
    int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

假设您在 merge 中有 n 个元素，在 arr1 和 arr2 中有 n/2 个元素，最坏情况下地图所需的内存将是是 (n * 0.75 + 1)*2 + ((n/2 + n/2) * 0.75 + 1)*2 等于 4 * (n * 0.75 + 1) = 3n + 4。您可以另外添加局部变量所需的 space，但它们实际上是微不足道的。

总而言之，这种方法具有 O(n) 运行时间，因此是渐近最优的，因为您必须“查看”每个值一次，尽管可能存在具有（显着）较小常量的实现。

就内存而言，肯定有比这少得多的实现，但很可能内存对于整数数组的现代硬件来说并不是一个大问题。

import java.util.*;

public class Application {
    public static void main(String[] args) {
        System.out.println(isMerge(new int[]{3, 1, 2, 2}, new int[]{2, 1, 1}, new int[]{3, 1, 2, 2, 2, 1, 1}));
        System.out.println(isMerge(new int[]{1, 2, 3}, new int[]{4, 5, 6}, new int[]{1, 2, 3, 4, 5, 6}));
        System.out.println(isMerge(new int[]{1, 2, 3}, new int[]{4, 5, 6}, new int[]{1, 4, 5, 2, 3, 6}));
        System.out.println(isMerge(new int[]{1, 2}, new int[]{2, 3}, new int[]{1, 2, 3, 2}));
        System.out.println(isMerge(new int[]{1, 2}, new int[]{3, 4}, new int[]{1, 2, 3, 4, 5}));
        System.out.println(isMerge(new int[]{1, 2}, new int[]{3, 4}, new int[]{1, 2, 5, 3, 4}));
        System.out.println(isMerge(new int[]{1, 2}, new int[]{3, 4}, new int[]{5, 1, 2, 3, 4}));
    }

    public static boolean isMerge(int[] arr1, int[] arr2, int[] merge) {
        // early out if we have less values in arr1 + arr2 then in merge or if merge is empty and any of the other is not
        // this could be changed to arr1.length + arr.length !0 merge.length when you don't want to allow this: arr1 = [1, 2], arr2=[3,4,5] and merge=[1,2,3] to return true. It does also make calculating the space easier and will reduce the average case runtime drastically for random inputs
        if (arr1.length + arr2.length < merge.length || (merge.length == 0 && (arr1.length != 0 || arr2.length != 0))) return false;
        // prevent possible rehashing by assigning maximum amount of possible values in the map divided by load factor but also use little memory as possible
        // one could change the load factor: increase -> more performance, more space or decrease -> less performance, less space and measure the performance
        // the calculation for the expected Map size is done like this in Guava and JDK8
        var twoArrValCount = new HashMap<Integer, Integer>((int)((float)(arr1.length + arr2.length) / 0.75f + 1.0f));
        var mergeValCount = new HashMap<Integer, Integer>((int)((float)merge.length / 0.75f + 1.0f));

        // determine longest array
        var longestOverall = Math.max(arr1.length, arr2.length);
        longestOverall = Math.max(longestOverall, merge.length);

        // count values in merge array and in two arrays combined
        for (int i = 0; i < longestOverall; i++) {
            // add 1 as count if its key is not present yet, add one to current value otherwise
            if (i < arr1.length) twoArrValCount.compute(arr1[i], (k, v) -> (v == null) ? 1 : v + 1);
            if (i < arr2.length) twoArrValCount.compute(arr2[i], (k, v) -> (v == null) ? 1 : v + 1);
            if (i < merge.length) mergeValCount.compute(merge[i], (k, v) -> (v == null) ? 1 : v + 1);
        }

        // compare both maps: if all values match return true, return false otherwise
        return mergeValCount
                .entrySet()
                .stream()
                .allMatch(entry -> {
                    // if map2 does not contain a key that is present in map1 -> return false
                    if (!twoArrValCount.containsKey(entry.getKey())) return false;
                    // return result of comparison: if match -> return true, if no match -> return false
                    // if you want to return true for e.g. arr1 = [1, 2], arr2=[3,4,5] and merge=[1,2,3]
                    return twoArrValCount.get(entry.getKey()) <= entry.getValue();
                    // if you want to return false for e.g. arr1 = [1, 2], arr2=[3,4,5] and merge=[1,2,3]
                    // return Objects.equals(twoArrValCount.get(entry.getKey()), entry.getValue())
                });
    }
}

预期输出：

true
true
true
true
false
false
false

检查一个数组是否是 2 个数组的合并

Check if an array is a merge of 2 arrays

java

arrays

algorithm

array-merge