算法 求助二维数组去重

ailen · 2018年10月28日 · 最后由 ailen 回复于 2018年10月29日 · 5942 次阅读

输入数组:

a = [
[0,1], [0, 2], [0, 3],
[0,1], [0, 2], [0, 3],[0, 4],
[1,0], [1, 1], [1, 2],[1, 3],
[1,0], [1, 1], [1, 2],[1, 3],[1,4]
]

要求写一个算法,找出 a 数组中长度最长的非子集数组,因为

[0,1], [0, 2], [0, 3]
[1,0], [1, 1], [1, 2],[1, 3],

分别是

[0,1], [0, 2], [0, 3],[0, 4]
[1,0], [1, 1], [1, 2],[1, 3],[1,4]

的子集,所以经过去重后应该得到输出

[
[0,1], [0, 2], [0, 3],[0, 4],
[1,0], [1, 1], [1, 2],[1, 3],[1,4]
]

目前用遍历方法实现了一个算法,请教大家有没有更高效的算法。

楼主的例子说了这么多,我的理解就是数组去重。。。

没咋倒腾过算法,自己写怎么都要遍历一次吧 (O(n) 的时间复杂度),随手写大概是这样:a.each_with_object({}){|ar, hsh| hsh[ar] = true}.keys,不知道能不能跑赢a.uniq! 。楼主把代码贴出来撒

spike76 回复

@spike76 感谢,我发现 uniq! 是正解,自己写的跟你的思路一样

需要 登录 后方可回复, 如果你还没有账号请 注册新账号