[描述] 给定两个长度相同的整数数组。设计一个可以判断它们是否相同的算法。 “相同”的定义是,如果这两个数组是有序排列的,则对应位置的元素应该相同。
[Example]
<1 2 3 4> = <3 1 2 4>
<1 2 3 4> != <3 4 1 1>
[局限]该算法需要恒定的额外空间和O(n)的运行时间。
最佳答案
(对于面试问题来说可能太复杂了。)
(可以先用O(N)的时间检查min、max、sum、sumsq等是否相等。)
使用no-extra-space radix sort对两个数组进行就地排序。 O(N) 时间复杂度,O(1) 空间。
然后使用通常的算法比较它们。 O(N) 时间复杂度,O(1) 空间。
(假设数组的 (max − min) 是 O(Nk) 且 k 有限。)
关于arrays - 比较两个具有相同长度的整数数组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2402255/