f*******w 发帖数: 1243 | 1 Maximum sum contiguous subsequence的变种
用O(nlogn)的方法来check一个实数序列里是否存在和为0的连续子序列
开始想着用divide and conquer,但是没想明白怎么combine左半部分和右半部分 |
l***e 发帖数: 6 | 2 s[i]=\sigma a[i] 对s排序 找相邻gap最小的
【在 f*******w 的大作中提到】 : Maximum sum contiguous subsequence的变种 : 用O(nlogn)的方法来check一个实数序列里是否存在和为0的连续子序列 : 开始想着用divide and conquer,但是没想明白怎么combine左半部分和右半部分
|
f*******w 发帖数: 1243 | 3
所以意思是如果存在和为0的子序列,对s排序之后一定有相等的2个元素吗?
好像是对的,谢谢!
【在 l***e 的大作中提到】 : s[i]=\sigma a[i] 对s排序 找相邻gap最小的
|
w*********r 发帖数: 2192 | 4 1. sorting A in ascending order
2. find the closest two points where A[i] < 0 < A[j]
3. initialize: left_p = i; right_p = j
4. if sum[left_p -> right_p] > 0; left_p--
else if (sum[left_p -> right_p] < 0); right_p++
【在 f*******w 的大作中提到】 : Maximum sum contiguous subsequence的变种 : 用O(nlogn)的方法来check一个实数序列里是否存在和为0的连续子序列 : 开始想着用divide and conquer,但是没想明白怎么combine左半部分和右半部分
|
f*******w 发帖数: 1243 | 5
我开始也是这么想的
可是不对啊,这样找到的是和为0的子序列
但是不能保证是连续子序列
【在 w*********r 的大作中提到】 : 1. sorting A in ascending order : 2. find the closest two points where A[i] < 0 < A[j] : 3. initialize: left_p = i; right_p = j : 4. if sum[left_p -> right_p] > 0; left_p-- : else if (sum[left_p -> right_p] < 0); right_p++
|
y*w 发帖数: 42 | 6 why ? sum[left_p -> right_p] is 连续的呀?
【在 f*******w 的大作中提到】 : : 我开始也是这么想的 : 可是不对啊,这样找到的是和为0的子序列 : 但是不能保证是连续子序列
|
f*******w 发帖数: 1243 | 7
因为你是排过序之后的连续
排序之前的不是被打乱了
【在 y*w 的大作中提到】 : why ? sum[left_p -> right_p] is 连续的呀?
|
g**u 发帖数: 583 | 8 how about this?
(1) define
b[i]=sum_{a[i]} {i=0,1,...,n-1}
(2) sort b[i]
(3) find the index j, k, such that
b[j]+b[k]=0, then we know in original array sum[ a[min{i,j}],..., a[
min{i,j}] ] =0 |
i*********7 发帖数: 348 | 9 通过A[i]序列得到sum[i]序列。
然后进行排序,排序的过程里要记录下它原先的index。
有相等的sum值就可以返回true了。
当然,也有O(n)的解法。
Double sum = 0;
HashSet hs = new HashSet
for(int i = 0; i < a.length; i++){
sum += a[i];
if(hs.contains(sum))
return true;
hs.add(sum);
}
return false; |
g**e 发帖数: 6127 | 10 This HashSet thing does not work. Avoid!
【在 i*********7 的大作中提到】 : 通过A[i]序列得到sum[i]序列。 : 然后进行排序,排序的过程里要记录下它原先的index。 : 有相等的sum值就可以返回true了。 : 当然,也有O(n)的解法。 : Double sum = 0; : HashSet hs = new HashSet : for(int i = 0; i < a.length; i++){ : sum += a[i]; : if(hs.contains(sum)) : return true;
|
|
|
i*********7 发帖数: 348 | 11 在Java里,HashSet是可以有的。
只是在C++里,hash_set是没有的。
要换成unordered_set。
【在 g**e 的大作中提到】 : This HashSet thing does not work. Avoid!
|
i*********7 发帖数: 348 | 12 public static boolean testDoubleHS(Double a[]){
Double sum = 0.0;
HashSet hs = new HashSet();
hs.add(sum);
for(int i = 0; i < a.length; i++){
sum += a[i];
if(hs.contains(sum))
return true;
hs.add(sum);
}
return false;
}
这个是我刚才在eclipse里面测试过了。应该是可以的。 |
g**e 发帖数: 6127 | 13 换台机器换个系统换个JVM就不一定可以了。关键问题在那个加法
[0.1, 0.2, -0.2] 当你加到第三个数的时候,很可能结果是0.10000000001,这时候
contains返回false
【在 i*********7 的大作中提到】 : public static boolean testDoubleHS(Double a[]){ : Double sum = 0.0; : HashSet hs = new HashSet(); : hs.add(sum); : for(int i = 0; i < a.length; i++){ : sum += a[i]; : if(hs.contains(sum)) : return true; : hs.add(sum); : }
|
i*********7 发帖数: 348 | 14 我明白你的意思。
双精度数的处理多少会有小数点后几位的偏差。
所以我自己才测试了一下。感觉数目比较小的时候适用。比较大的情况下我也不好说。
这本身就是C++和Java对浮点数的处理导致的。算法本身是没错的。
我也就提供一下思路。因为毕竟就算法本身而言,这个是time on, space on
而对sum排序后再比较的算法,是time onlogn, space on的。要稍微好一些。
【在 g**e 的大作中提到】 : 换台机器换个系统换个JVM就不一定可以了。关键问题在那个加法 : [0.1, 0.2, -0.2] 当你加到第三个数的时候,很可能结果是0.10000000001,这时候 : contains返回false
|
t****a 发帖数: 1212 | 15 谢谢提示。据此写clojure code如下,调试成功
(use 'incanter.core)
(defn subseqzero? [a]
(let [ac (cumulative-sum (cons 0 a))
acf (frequencies ac)]
(some #(> % 1) (vals acf))))
(def a [1 -3 4 1 -2 9])
(subseqzero? a) ; true
(def a [1 -3 4 3 -2 9])
(subseqzero? a) ; nil
【在 i*********7 的大作中提到】 : 通过A[i]序列得到sum[i]序列。 : 然后进行排序,排序的过程里要记录下它原先的index。 : 有相等的sum值就可以返回true了。 : 当然,也有O(n)的解法。 : Double sum = 0; : HashSet hs = new HashSet : for(int i = 0; i < a.length; i++){ : sum += a[i]; : if(hs.contains(sum)) : return true;
|
i*********7 发帖数: 348 | 16 我擦。。你的什么代码。。完全看不懂。。
好吧。。clojure是啥。。。
【在 t****a 的大作中提到】 : 谢谢提示。据此写clojure code如下,调试成功 : (use 'incanter.core) : (defn subseqzero? [a] : (let [ac (cumulative-sum (cons 0 a)) : acf (frequencies ac)] : (some #(> % 1) (vals acf)))) : (def a [1 -3 4 1 -2 9]) : (subseqzero? a) ; true : (def a [1 -3 4 3 -2 9]) : (subseqzero? a) ; nil
|
t********e 发帖数: 344 | 17 请问sum[i]序列是什么?
【在 i*********7 的大作中提到】 : 通过A[i]序列得到sum[i]序列。 : 然后进行排序,排序的过程里要记录下它原先的index。 : 有相等的sum值就可以返回true了。 : 当然,也有O(n)的解法。 : Double sum = 0; : HashSet hs = new HashSet : for(int i = 0; i < a.length; i++){ : sum += a[i]; : if(hs.contains(sum)) : return true;
|