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

Question

我有兴趣创建一个具有运行时间和 space 约束的简单数组问题。看来我找到了解决问题的方法。请阅读以下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

我不 Java 识字，但你能不能只对每个数组进行排序，然后迭代检查排序后的数组的每个元素是否相等？

Answer 2

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

这显然是不可能的，因为多重集的数量是无限的，但是如果space是常数，那么指纹的数量是有限的。所以你不可避免地会发现两个不同的多重集映射到同一个指纹的例子。

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

Proof: Check if two integer arrays are permutations of each other using linear time and constant space

algorithm

time-complexity

permutation

proof

space-complexity