面试题: 未排序等长 数组, 判断是否互为 permutation

Question

unsorted integer arrays A and B of equal size, determine if B is
permutation of A. 要求O(n) time and O(1) extra space.

Answer 1

首先O(1)的存储说明这题肯定是用比较校验值的方式。然后这题除了复杂度要求外，主要是两个要求：一是顺序无关，那么有些对顺序敏感的算法就可以放弃了。二是强无碰撞性。

所以我的方法是先读第一个数，进行md5「也可以选择其他摘要算法」后以整数或整数数组「看你用的语言是否自带大数库」的格式存入校验位。然后依次读后面的数并md5之后与校验位做异或将结果存入校验位。最后比较两数组的校验位即可。
我想了一下，估计是可以满足强弱无碰撞的，至于证明，我就真的不会了。

---

补充，上面异或的方式经过@brayden提醒是有缺陷的，那就改成求和忽略进位吧。每次求和后和(1<<256-1)求与，保留后256bit。

Answer 2

http://stackoverflow.com/questions/10929185/are-two-arrays-permutation-of-each-other

Answer 3

根据 @Chobits 的链接找到了另一个对应问题.

http://stackoverflow.com/questions/10639661/check-if-array-b-is-a-permutation-of-a

最高票的意思是, 弄一个长度为 2^32 的数组作为 hash table, 因为 2^32 是常数,,, 所以是 O(1)... 哭了...