s********0
发帖数: 34 | 1 一个数组只有1，0 元素，找出所有连续区间的数目， 满足该区间1的个数>=0的数目。
比如a:[1, 0, 1, 0, 0, 1]
结果为11: (3+4+1+2+1)
[1], [1], [1], =>3
[1, 0], [0, 1], [1, 0], [0, 1], =>4
[1, 0, 1], =>1
[1, 0, 1, 0], [1, 0, 0, 1], =>2
[1, 0, 1, 0, 0, 1] => 1
要求复杂度 nlgn.
O(n^2)的复杂度比较容易想，0置换成-1，然后求前缀和数组sum。
nlgn我是这么想的：
还是0换成-1，还是求前缀数组，然后对每个sum[i]求 前面小于等于它的个数，这步可
以二分。
比如某一步的时候 sum = 0 有1个， sum = 1 有2个， sum =2 有3个，
则sum <= 0: 1个, sum <= 1: 3个, sum <= 2: 6个 这个是单调递增的
维护这个单调队列 可以用树状数组
觉得实现起来有点麻烦，请教有别的方法没？thanks | U***A
发帖数: 849 | | s********0
发帖数: 34 | 3 应该是dp 只是没想好怎么dp -______- | l*********8
发帖数: 4642 | 4 为什么[0,1,0], [1,0,0], [0,0,1], [0,1,0,0], [1,0,1,0,0], [0, 1, 0, 0, 1]不满
足条件？
如果满足条件的话，应该有17个区间。 而且O(n)时间可以求解。
【在 s********0 的大作中提到】
: 一个数组只有1，0 元素，找出所有连续区间的数目， 满足该区间1的个数>=0的数目。
: 比如a:[1, 0, 1, 0, 0, 1]
: 结果为11: (3+4+1+2+1)
: [1], [1], [1], =>3
: [1, 0], [0, 1], [1, 0], [0, 1], =>4
: [1, 0, 1], =>1
: [1, 0, 1, 0], [1, 0, 0, 1], =>2
: [1, 0, 1, 0, 0, 1] => 1
: 要求复杂度 nlgn.
: O(n^2)的复杂度比较容易想，0置换成-1，然后求前缀和数组sum。
| s********0
发帖数: 34 | 5 不好意思 可能没描述清楚
[0,1,0] 有1个‘1’， 2个‘0’， 所以1的个数小于0的个数 不成立
所以题目通俗点讲 就是
如果是1， -1 (0替换成-1）组成的数组的话，就是找出所有子数组的个数，要求子数
组和>= 0 | m*****n
发帖数: 2152 | 6 据我所知，DP算法好像还没有能突破n^2的。
你可以试试Binary indexed tree。
【在 s********0 的大作中提到】
: 应该是dp 只是没想好怎么dp -______-
| f******t
发帖数: 18 | 7 難道不是逆序對(這裡是順序)數目麼？對sum數組用歸並排序吧？ | l*********8
发帖数: 4642 | 8 谢谢解释。
我觉得还是可以用O(n)时间求解。
【在 s********0 的大作中提到】
: 不好意思 可能没描述清楚
: [0,1,0] 有1个‘1’， 2个‘0’， 所以1的个数小于0的个数 不成立
: 所以题目通俗点讲 就是
: 如果是1， -1 (0替换成-1）组成的数组的话，就是找出所有子数组的个数，要求子数
: 组和>= 0
| s********0
发帖数: 34 | 9 赞 转化成这个就可以了 nlgn归并就可以
【在 f******t 的大作中提到】
: 難道不是逆序對(這裡是順序)數目麼？對sum數組用歸並排序吧？
| l*********8
发帖数: 4642 | 10 nice!
【在 s********0 的大作中提到】
: 赞 转化成这个就可以了 nlgn归并就可以
| m****c
发帖数: 252 | 11 有点不太明白，这个前缀和数组sum怎么求啊。
【在 s********0 的大作中提到】
: 一个数组只有1，0 元素，找出所有连续区间的数目， 满足该区间1的个数>=0的数目。
: 比如a:[1, 0, 1, 0, 0, 1]
: 结果为11: (3+4+1+2+1)
: [1], [1], [1], =>3
: [1, 0], [0, 1], [1, 0], [0, 1], =>4
: [1, 0, 1], =>1
: [1, 0, 1, 0], [1, 0, 0, 1], =>2
: [1, 0, 1, 0, 0, 1] => 1
: 要求复杂度 nlgn.
: O(n^2)的复杂度比较容易想，0置换成-1，然后求前缀和数组sum。
|
|
