一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 5003|回复: 14
收起左侧

[Leetcode] 关于4 Sum O(n^2logn)解法的问题

[复制链接] |试试Instant~ |关注本帖
eaglesky1990 发表于 2014-8-5 22:41:06 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
Leetcode中4sum的题目是这样的:

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:
Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
The solution set must not contain duplicate quadruplets.

For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

    A solution set is:
    (-1,  0, 0, 1)
    (-2, -1, 1, 2)
    (-2,  0, 0, 2)
我知道这题的O(n^3)的解法,不过网上很多人说给出了O(n^2logn)的算法, 但这些算法个人觉得实际上并没有处理好S中重复和的问题。比如这篇文章的讨论:http://tech-wonderland.net/blog/ ... html#comment-12572. 该文中Hash解法复杂度个人觉得并没有快于O(n^3)。
还有这里的解法:http://www.geeksforgeeks.org/fin ... given-value-set-2/.
以及这里的解法: http://stackoverflow.com/questio ... to-a-given-number-x

算法思路都是把所有pair的和以及相应两数的index存起来,将四数求和的问题转为二数求和。接下来一种思路是先将存起来的数排序(O(n^2 log n^2), 然后夹逼。注意夹逼时针对的数组中的每个元素实际上是两数和, 会有很多组合,所以如果夹逼时两元素和 == target, 还需要检查每个元素重复值所对应的两个数,这样一来因为一共有O(n^2)个元素,很有可能时间复杂度是O(n^4)。

另外一种思路是所有的pair和存到hashtable中。不过因为一个和可能对应多种组合,个人觉得应该用hash-multimap。这个具体代码在Leetcode题解(C++)版中给出了。 这个multimap里key是两数和,value是两数index,可能有多个,所以比较时也应该所有value对应的元素相互都比较才行,总复杂度感觉也不会是O(n^2)。

不知大家做过此题的人想法怎样。我说的可能不清楚,但很希望能和大家讨论一下此题。

谢谢!
Kimurate 发表于 2014-8-6 09:30:52 | 显示全部楼层
本帖最后由 Kimurate 于 2014-8-5 18:44 编辑

感觉你写的有点乱,不知道是我饿着肚子的原因还是你没想清楚……
你给的第一个链接我看过,有些许错误信息,而且 k-sum 的代码逻辑至少在 java 版本是会超时。

讲讲正题。以下都是我个人理解,仅供参考,欢迎吐槽。

2 sum 的 hashtable 解法是不需要排序的,O(n) 就可以。
对 4sum 来说,排序是必须的,先 n log(n),
在 LeetCode 里,4sum 要规约成 2sum + 2sum,我还没发现别的不超时的解法,所以这个解法是 O(nlogn + n^2 logn)
注意这里的 2sum 和单独 2sum 有所不同,我待会贴个链接。

早些年有论文指出,k-sum 问题的时间复杂度的理论下界大约是 N^(k/2) (具体我忘了,和 k 的奇偶有关),
其最快算法的思想即是把取 k 个数的问题看成取 k/2 个数,然后验证 sub-sum pair 的和是否是目标值。
我前些日子正好做了这道题,实现了这个算法,可以用同一段代码过 3 sum 和 4 sum。
http://lifexplorer.me/leetcode-3sum-4sum-and-k-sum/

k-sum 问题可说是好多 LeetCode 题目的结合版,写得超长,从 3sum 到 4sum 到 k-sum,没有一小时估计读不下来。
回复 支持 反对

使用道具 举报

 楼主| eaglesky1990 发表于 2014-8-6 15:25:04 | 显示全部楼层
Kimurate 发表于 2014-8-6 09:30
感觉你写的有点乱,不知道是我饿着肚子的原因还是你没想清楚……
你给的第一个链接我看过,有些许错误信息 ...

谢谢你的链接,该文章讲得很赞,代码我看了看,算法应该是没问题的。不过能否解释一下算法复杂度为何是O(n^2logn)呢?当存在重复和时,实际执行时是三重for循环,worst case的时间似乎是n^3吧?(https://oj.leetcode.com/discuss/3950/tle-on-4sum-using-hashtable 下边代码的回复似乎也是同样意思)
回复 支持 反对

使用道具 举报

Sun 发表于 2014-8-6 22:42:49 | 显示全部楼层

贴一下我的代码吧,最内层循环是个binary search,所以是O(lg(n)),再加上外层两个for循环,n^2lg(n)

https://github.com/mitcc/AlgoSol ... etcode/FourSum.java
回复 支持 反对

使用道具 举报

 楼主| eaglesky1990 发表于 2014-8-6 23:14:08 | 显示全部楼层
Sun 发表于 2014-8-6 22:42
贴一下我的代码吧,最内层循环是个binary search,所以是O(lg(n)),再加上外层两个for循环,n^2lg(n)

...

最内循环不能叫binary search吧。。。while里边的本质上是双向夹逼,是线性时间,所以总共是O(n^3)的。Worst case是: S = { 1, 2, 3, 4, 5, 6}, target = 1000。
回复 支持 反对

使用道具 举报

Sun 发表于 2014-8-7 02:00:05 | 显示全部楼层
eaglesky1990 发表于 2014-8-6 23:14
最内循环不能叫binary search吧。。。while里边的本质上是双向夹逼,是线性时间,所以总共是O(n^3)的。Wo ...

你是对的,我搞错了,我那个的确还是O(n^3)的
回复 支持 反对

使用道具 举报

Kimurate 发表于 2014-8-7 11:12:57 | 显示全部楼层
eaglesky1990 发表于 2014-8-5 23:25
谢谢你的链接,该文章讲得很赞,代码我看了看,算法应该是没问题的。不过能否解释一下算法复杂度为何是O( ...

复杂度:2sum里,for循环中每次要 search,时间是 logn,所以2sum 复杂度应该是 O(nlogn),我之前说错了。4sum里,外面套一个分割元素的循环,n,然后里面是并排的两个2sum,你可以把他们合成一个 n for来看,加上每次 containsKey 需要 log (n^2)(最多有 n^2 个元素),所以最终是n^2 log(n^2),化成n^2 (2 log n),去掉常数就可以了。
回复 支持 反对

使用道具 举报

Kimurate 发表于 2014-8-7 11:19:10 | 显示全部楼层
eaglesky1990 发表于 2014-8-5 23:25
谢谢你的链接,该文章讲得很赞,代码我看了看,算法应该是没问题的。不过能否解释一下算法复杂度为何是O( ...

关于重复的问题,我认为hash 的方法里总可能遇到最坏时间复杂度,也和hashtable的实现有关,不知道该怎么说
回复 支持 反对

使用道具 举报

 楼主| eaglesky1990 发表于 2014-8-7 11:39:57 | 显示全部楼层
Kimurate 发表于 2014-8-7 11:12
复杂度:2sum里,for循环中每次要 search,时间是 logn,所以2sum 复杂度应该是 O(nlogn),我之前说错了 ...

不知你说的是否是这个代码https://oj.leetcode.com/discuss/3950/tle-on-4sum-using-hashtable

这个代码里,内层两个并排的for循环不是问题,问题是在第一个内循环里边还有一个小循环:
  1. for (auto &p: hash[target - a]) {
  2.                         vector<int> b = {p.first, p.second, num<i>, num[j]};
  3.                         ans.insert(b);
  4.    }</i>
复制代码
这里的p会遍历所有和为target - a的pair,当存在不知一组pair的时候,整体的复杂度就不是O(n^2logn)了吧。
我所说的重复就是这个,即当存在多组不同的数对但和是一样的时候,并不是hashtable里边那个collision。
回复 支持 反对

使用道具 举报

Kimurate 发表于 2014-8-8 00:45:28 | 显示全部楼层
eaglesky1990 发表于 2014-8-6 19:39
不知你说的是否是这个代码https://oj.leetcode.com/discuss/3950/tle-on-4sum-using-hashtable

这个代 ...

key是2sum的值,那就还是hash碰撞,这里的hash有两层,第二层没碰撞罢了,但你说的这种值一样,元素组成都不一样的情况,不可能出现,因为数组已经经过排序
回复 支持 反对

使用道具 举报

 楼主| eaglesky1990 发表于 2014-8-8 08:57:59 | 显示全部楼层
本帖最后由 eaglesky1990 于 2014-8-8 09:19 编辑
Kimurate 发表于 2014-8-8 00:45
key是2sum的值,那就还是hash碰撞,这里的hash有两层,第二层没碰撞罢了,但你说的这种值一样,元素组成 ...

数组排好序了,和还是有可能是一样的吧?比如: S = {1, 2, 3, 4, 5, 6, 7, 8} 。 考虑i = 6 时,因为1+6 = 2+5 = 3+4 = 7, 所以对应于7的set里存在有三组pair,当j = 7, target = 22时,  此时 a = S[6] + S[7] = 15, target - a = 7, hash[7]这个set里就有三组pair,第三层for循环就要跑三次了。换个角度看,如果这种和相同的情况没有,那也没有必要用set了吧, 第三层for循环又有什么意义呢?
回复 支持 反对

使用道具 举报

Kimurate 发表于 2014-8-8 10:56:57 | 显示全部楼层
eaglesky1990 发表于 2014-8-7 16:57
数组排好序了,和还是有可能是一样的吧?比如: S = {1, 2, 3, 4, 5, 6, 7, 8} 。 考虑i = 6 时,因为1+6 ...

咳咳,不可能的,你没仔细看那个c++代码的逻辑。
i=6时,不是1+6, 2+5, 3+4, 而是1+6, 2+6,3+6, ... 5+6, 所以一次循环里,不存在一个和对应多个二元组的情况。
用set是因为从[1,1,1,1,2,2,2] 取出和为6的四元组时,会有很多重复的四元组。
回复 支持 反对

使用道具 举报

 楼主| eaglesky1990 发表于 2014-8-8 12:15:09 | 显示全部楼层
Kimurate 发表于 2014-8-8 10:56
咳咳,不可能的,你没仔细看那个c++代码的逻辑。
i=6时,不是1+6, 2+5, 3+4, 而是1+6, 2+6,3+6, ... 5+ ...

我的理解是: i 是 从 0 开始循环的, i 值达到 6 之前必然先经过5, 而i = 5 时 1+ 6, 2 + 6, 3 + 6 ... 5 + 6 被放入相应set; i = 4 时是1 +  5, 2 + 5, 3 + 5, 4 + 5 被放入相应set 。 所以 i = 6 时, hashtable中存有前边所有两两组合的pair, 这样做也才是保证不丢解。
回复 支持 反对

使用道具 举报

Kimurate 发表于 2014-8-8 12:58:34 | 显示全部楼层
eaglesky1990 发表于 2014-8-7 20:15
我的理解是: i 是 从 0 开始循环的, i 值达到 6 之前必然先经过5, 而i = 5 时 1+ 6, 2 + 6, 3 + 6 ...  ...

恩,有道理。这个O(n^3)应该是最坏情况,但即便从构造的例子中来看,这个情况也是非常局部的,不知道能否扩展到整体,把整个算法都变成O(n^3)。
两部分的2sum只会越来越大,和跟二元组不会总有很多重复的。感觉上重复二元组的数量好像是先从少变多,然后又变少了,应该不是O(n),但我不知道怎么证明。

详细看看这个 http://cs.stackexchange.com/ques ... -3sum-k-sum-problem

好多细节我还是没搞懂啊 = =。
回复 支持 反对

使用道具 举报

3652ltc 发表于 2014-8-9 12:53:39 | 显示全部楼层
我觉得关键是 如何在n^2logn复杂度下生成不含重复元素的 pairs
knuth好像有写过generate all combinations 我也没太懂,还希望lz多多指教指教,我想了半天实在没啥思路。。哭
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 15:29

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表