algorithm - 证明:使用线性时间和常量空间检查两个整数数组是否是彼此的排列

Question

我有兴趣创建一个具有运行时间和空间限制的简单数组问题。看来我找到了解决问题的方法。请阅读以下java代码中问题的初始描述注释:

 /*
 * Problem: Given two integer arrays, a and b, return whether array a is a permutation of array b.
 * Running time complexity: O(n)
 * Space complexity: O(1)
 * Example 1:
 * a = [1, 2, -3]
 * b = [2, 3, 1]
 * false
 * Example 2:
 * a = [1, 2, 3]
 * b = [0, 1]
 * false
 * Example 3:
 * a = [2, 7, 3, 5]
 * b = [5, 7, 2, 3]
 * true
 * Example 4:
 * a = [1, -2, 10000]
 * b = [10000, 1, -2]
 * true
 * Example 5:
 * a = [1, 2, 2, 3]
 * b = [3, 2, 1, 3]
 * false
 * Example 6:
 * a = [2, 2, 4, 4]
 * b = [3, 3, 3, 3]
 * false
 * Example 7:
 * a = [4, 4, 2, 2, 4, 4]
 * b = [4, 3, 3, 3, 3, 4]
 * false
 * ----------------------
 * Input is two space separated lines of integers
 * Output is true or false
 * Terminal Example:
 * 1 4 9 25
 * 4 25 9 2
 * false
 * ----------------------
 * Solution:
 * 1. Average displacement (delta) between the elements of array a and array b equals 0
 * AND
 * 2. xor-ing all of the values between the elements of array a and array b equals 0
 * AND
 * 3. mins are the same and maxs are the same
 * @author (David Brewster)
 * @version (27.01.2016) (requires java 1.8)
 */

import java.util.Scanner;
import java.util.Arrays;
public class ArrayProb
{
    public static int xorComparison(int[] a, int[] b, int i, int xortotal)
    {
        return i == a.length ?
                xortotal : xorComparison(a, b, i + 1, xortotal ^ a[i] ^ b[i]);
    }
    public static int deltaComparison(int[] a, int[] b, int i, int deltatotal)
    {
        return i == a.length ?
                deltatotal : deltaComparison(a, b, i + 1, deltatotal + a[i] - b[i]);
    }
    public static int minComparison(int[] a, int[] b, int i, int amin, int bmin)
    {
        return i == a.length ?
                amin-bmin : minComparison(a, b, i + 1,
                a[i] < amin ? a[i] : amin,
                b[i] < bmin ? b[i] : bmin);
    }
    public static int maxComparison(int[] a, int[] b, int i, int amax, int bmax)
    {
        return i == a.length ?
                amax-bmax : maxComparison(a, b, i+1,
                a[i] > amax ? a[i] : amax,
                b[i] > bmax ? b[i] : bmax);
    }
    public static boolean arePermutations(int[] a, int[] b)
    {
        if (a.length == b.length)
        {
            boolean d = xorComparison(a, b, 0, 0) == 0;
            boolean e = deltaComparison(a, b, 0, 0) == 0;
            boolean f = maxComparison(a, b, 0, Integer.MIN_VALUE, Integer.MIN_VALUE) == 0;
            boolean g = minComparison(a, b, 0, Integer.MAX_VALUE, Integer.MAX_VALUE) == 0;
            return d && e && f && g;
        }
        else
        {
            return false;
        }
    }
    public static void main(String[] args)
    {
        Scanner input = new Scanner(System.in);
        int[] a = Arrays.stream(input.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int[] b = Arrays.stream(input.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        System.out.println(arePermutations(a, b));
    }
}

即使认为该算法似乎适用于大多数情况(至少我目前测试过的所有情况)，我将如何证明该解决方案在 100% 的时间内都是正确的？

Answer 1

您基本上要做的是计算每个数组(代表一个多重集)的固定大小的指纹，然后通过比较指纹来确定多重集的相等性。

这显然是不可能的，因为多重集的数量是无限的，但如果空间不变，指纹的数量是有限的。因此，您不可避免地会发现两个不同的多重集映射到同一指纹的示例。