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

Question

实现一个函数，检查给定的数组是否可以以任何方式被构造为另外两个数组的合并。

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数组中值的出现次数。这可以在三个数组中最长的一个简单循环中完成。当然，只有在合并数组中的值比其他两个数组加起来的值少的时候才会出现这种情况。如果是这种情况，我们可以立即返回false，因为没有办法从两个数组合并。如果merge为空并且其他两个数组中的任何一个不是，我也返回false。

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

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

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

• formerge:(n * 0.75 + 1)*2
• forarr1andarr2:((a + b) * 0.75 + 1)*2

下一个2的幂将被Java内部用于数组的容量，所以在最坏的情况下，我们需要的空间量是实际存储值所需的两倍，因此*2。

参见JavaHashMap中决定后备数组大小的代码:

/**
* 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。您可以额外添加局部变量所需的空间，但它们实际上是相当微不足道的。

总而言之，这种方法具有O(n)运行时间，因此是渐近最优的，因为您将不得不"查看"。每个值一次，尽管可能有(明显)更小的常量的实现。

在内存方面，肯定有比这少得多的实现，但是对于Integer数组，在现代硬件上，内存很可能不是一个大问题。

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