z**z
发帖数: 222 | 1 You have an array of 0s and 1s and you want to output all the intervals (i,
j) where the number of 0s and numbers of 1s are equal.
Example
index = 0 1 2 3 4 5 6 7 8
array = 0 1 0 0 1 1 1 1 0
One interval is (0, 1) because there the number of 0 and 1 are equal. There
are many other intervals, find all of them in linear time.
How can this be done in O(n)??
find all intervals, not find the longest interval.
Thanks in advance. | F**r
发帖数: 84 | 2 不可能，给你个反例
0101010101....
最好的情况O(n^2)
intervals (i,
equal. There
【在 z**z 的大作中提到】
: You have an array of 0s and 1s and you want to output all the intervals (i,
: j) where the number of 0s and numbers of 1s are equal.
: Example
: index = 0 1 2 3 4 5 6 7 8
: array = 0 1 0 0 1 1 1 1 0
: One interval is (0, 1) because there the number of 0 and 1 are equal. There
: are many other intervals, find all of them in linear time.
: How can this be done in O(n)??
: find all intervals, not find the longest interval.
: Thanks in advance.
| M**u
发帖数: 10158 | 3 how about
0 1 0 1 0 1 ...
it will have O(n^2) answers... how can it be done in linear time?
,
There
【在 z**z 的大作中提到】
: You have an array of 0s and 1s and you want to output all the intervals (i,
: j) where the number of 0s and numbers of 1s are equal.
: Example
: index = 0 1 2 3 4 5 6 7 8
: array = 0 1 0 0 1 1 1 1 0
: One interval is (0, 1) because there the number of 0 and 1 are equal. There
: are many other intervals, find all of them in linear time.
: How can this be done in O(n)??
: find all intervals, not find the longest interval.
: Thanks in advance.
| b**********r
发帖数: 91 | 4 Build an array S[i] = NumOfOnes - NumberOfZeros from index 0 to i of the
original array
then if the interval i to j contains the same number of zero and ones
<==> S[i] == S[j]
Scan through S and use hash map, then all pairs has the same value gives
you all pairs of i, j. It's O(n) time
intervals (i,
There
【在 z**z 的大作中提到】
: You have an array of 0s and 1s and you want to output all the intervals (i,
: j) where the number of 0s and numbers of 1s are equal.
: Example
: index = 0 1 2 3 4 5 6 7 8
: array = 0 1 0 0 1 1 1 1 0
: One interval is (0, 1) because there the number of 0 and 1 are equal. There
: are many other intervals, find all of them in linear time.
: How can this be done in O(n)??
: find all intervals, not find the longest interval.
: Thanks in advance.
| r*******y
发帖数: 1081 | 5 smart
【在 b**********r 的大作中提到】
: Build an array S[i] = NumOfOnes - NumberOfZeros from index 0 to i of the
: original array
: then if the interval i to j contains the same number of zero and ones
: <==> S[i] == S[j]
: Scan through S and use hash map, then all pairs has the same value gives
: you all pairs of i, j. It's O(n) time
:
: intervals (i,
: There
| g**e
发帖数: 6127 | 6 output the pairs would cost O(n^2)
DP is the right approach, but I think it takes O(n^2)
【在 b**********r 的大作中提到】
: Build an array S[i] = NumOfOnes - NumberOfZeros from index 0 to i of the
: original array
: then if the interval i to j contains the same number of zero and ones
: <==> S[i] == S[j]
: Scan through S and use hash map, then all pairs has the same value gives
: you all pairs of i, j. It's O(n) time
:
: intervals (i,
: There
| r*******y
发帖数: 1081 | 7 Using a hashmap to scan S to find the pairs will just cost O(n)
【在 g**e 的大作中提到】
: output the pairs would cost O(n^2)
: DP is the right approach, but I think it takes O(n^2)
| g**e
发帖数: 6127 | 8 how do you output at most n^2 pairs in O(n)?
【在 r*******y 的大作中提到】
: Using a hashmap to scan S to find the pairs will just cost O(n)
| s*****n
发帖数: 5488 | 9 看不太懂算法。是说，(2,3) (1,2)是一对output? 漏了(0,1)?
0 1
s[0] = -1;
s[i] = 0;
0 1 0 1
[s0] = -1;
s[1]= 0;
s[2] = -1;
s[3] = 0;
【在 b**********r 的大作中提到】
: Build an array S[i] = NumOfOnes - NumberOfZeros from index 0 to i of the
: original array
: then if the interval i to j contains the same number of zero and ones
: <==> S[i] == S[j]
: Scan through S and use hash map, then all pairs has the same value gives
: you all pairs of i, j. It's O(n) time
:
: intervals (i,
: There
| M**u
发帖数: 10158 | 10 good!
【在 b**********r 的大作中提到】
: Build an array S[i] = NumOfOnes - NumberOfZeros from index 0 to i of the
: original array
: then if the interval i to j contains the same number of zero and ones
: <==> S[i] == S[j]
: Scan through S and use hash map, then all pairs has the same value gives
: you all pairs of i, j. It's O(n) time
:
: intervals (i,
: There
| r*******y
发帖数: 1081 | 11 you are right.
say S[2] = 1, S[4] = 1, S[7] = 1, S[8] = 1
then in the hashmap H we will have
H[1] = {2, 4, 7, 8}
if we only output 2 4 7 8, then it is O(n)
【在 g**e 的大作中提到】
: how do you output at most n^2 pairs in O(n)?
| c*******n
发帖数: 63 | |
|
