Java-如何高效判断两个随机数组里面的元素是否完全相同?

Java-如何高效判断两个随机数组里面的元素是否完全相同?

泛泛之交 发布于 2017-03-04 字数 679 浏览 1244 回复 5

如何高效判断两个随机数组里面的元素是否完全相同?

-------------------------
好吧! 我告诉下答案吧! 我们只讨论数组长度等的情况,如果不等当然不同了。
我在《数学之美》里看到的,比较快速的算法。先排序再比较,复杂度为 O(Nlog(N)),因为最快的排序是这个复杂度,然后一一比较 O(N).
2。
还有一种 O(N)的算法,是先hash 一个数组,然后比较。
3。将数组里面的元素先映射为md5等footprint,然后 把两个数组直接相加比较和是否相等,O(N)。
这种方法有非常小的概率判断错误,就是元素不同和相同,但是概率非常小。《数学之美》里面有讨论。

个人觉得后面两种比较有新意,而且效率高,所以放这儿了,献丑了。
可继续讨论,请勿拍,谢谢!

如果你对这篇文章有疑问,欢迎到本站 社区 发帖提问或使用手Q扫描下方二维码加群参与讨论,获取更多帮助。

扫码加入群聊

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(5

想挽留 2017-10-15 5 楼

用API一定比你自己写的快。。比如上述的 java.util.Arrays.equals(byte[], byte[])

归属感 2017-06-23 4 楼

我是搞前端的但是以前也考虑过这种问题,讲讲思路吧...我的思路是先统计在比较
比较是对于统计后的数据进行比较,有点是重复数据越多,时间越短,重复数据越少,耗损时间越多
代码基本测试代码如下,这是js代码简单的东西大家应该看得懂
var arrPar = [], subArr = [], i = 1999999; /源数组包含数字个数/

//循环生成数组,随机数为0-19循环200W-1次将会存在大量重复
while (i--) {

subArr.push(parseInt(Math.random() * 20));

arrPar.push(parseInt(Math.random() * 20));

}
//获取测试前时间
var d1 = new Date().getTime();

//测试
var data1 = arrPar.Vs(subArr);

//整个完成时间
alert(new Date().getTime() - d1);

具体代码写在csnd有兴趣可以去看看
http://blog.csdn.net/chaiyining007/article/details/7649109

虐人心 2017-05-07 3 楼

LZ基本都说了。
不过md5是不可取的md5本身就有N的复杂度的……虽然是平行的。。
不过如果数据范围小的话开个桶塞进去也是可以的……就是hash啦……如果只是算法层面上的讨论的话LZ给出的第一种应该是比较好的答案,适用范围广,保证正确。不过根据实际情况的不同倒是可以有所讨论。

偏爱自由 2017-03-08 2 楼

试试 java.util.Arrays.equals(byte[], byte[])

夜无邪 2017-03-07 1 楼

有没有想过用判断均值和方差是否都相同以及二分的思想,有反例请指出
A=[6 3 1 8 2]
B=[2 1 8 5 4]
A的均值=4 B的均值 4
A的方差=4+1+9+16+4=34
B的方差=4+9+16+1+0=30
所以不同

如果相同,如下边A与B的均值和方差是相同的,取大于或者小于均值的数继续构成数组
A=[1 3 3 5 6 8 9]
B=[1 2 4 5 7 7 9]

A‘=[1 3 3]
B’=[1 2 4]
然后继续比较A‘与B’的均值和方差,依此叠带,如果依然相同则循环该过程直到只剩一个数为止,如果剩下的数相同则原数组相同,不同则不同,一般情况下如果A与B不同我认为叠带两次即可判定