[提问]检查2个数组是否内容相同

lin5161678 发布于 2020-04-02 17:18， 2495 次点击

2个长度相同的整型数组
判断是否都是相同元素元素次序不同
比如 [1,2,3,4][4,2,3,1]判断为相同数组

不知道有什么简单点的方法可以处理这个问题

9 回复

wmf20142020-04-02 17:40

异或一次

纯蓝之刃2020-04-02 17:48

先将两个数组按大小顺序排序，然后逐个比较数组中元素是否相同，遇到不同的就跳出输出不相等。

lin51616782020-04-02 17:59

以下是引用wmf2014在2020-4-2 17:40:04的发言：

异或一次

哈哈哈和我想一样和我错一样
我就说不会只有我一个人掉坑里的
这样做有陷阱

猜猜看是什么

lin51616782020-04-02 17:59

以下是引用纯蓝之刃在2020-4-2 17:48:02的发言：

先将两个数组按大小顺序排序，然后逐个比较数组中元素是否相同，遇到不同的就跳出输出不相等。

这样的确能得到正确结果
如果有更好的办法就好了
我想多了解一些新的思路

wmf20142020-04-02 18:13

对0不异或，或者既异或又求和，反正O(n)解决。主要陷阱是元素单边成对，和或差就不同。

[此贴子已经被作者于2020-4-2 18:26编辑过]

lin51616782020-04-02 18:25

回复 6楼 wmf2014

和有没有异或0 没关系
异或加求和也不行
按照目前这个题目 O(n)算法可能是陷阱
目前我没找到一个合适的O(n)算法处理
比如
[2,2,5,5]
[3,3,4,4]
你求和也好异或也好
都会认为是相同数组
实际上不是

异或需要额外多一个条件
数组元素不能重复
我之前也是忘记考虑这种特殊情况

wmf20142020-04-02 18:29

回复 6楼 wmf2014

见6楼修改后的回复

lin51616782020-04-02 18:30

以下是引用wmf2014在2020-4-2 18:29:08的发言：

见6楼修改后的回复

修改后还是没解决
[2,2,5,5][3,3,4,4]
判定失败呀

#10

wmf20142020-04-02 18:56

要不乘，为防止溢出，元素相乘模一个固定的数，元素相同则余数肯定相等。
实在不行，把偶数个数，3、5、7倍数的个数都统计一下，差不多是md5加密的碰撞概率了。
还有一个方法是：元素统一加一个相同数，异或一次右移一次，直到所有元素为0每次异或都相等则相同，不过不是O(n)了。

[此贴子已经被作者于2020-4-2 19:19编辑过]