z*********8
发帖数: 2070 | 1 一个int array 长度为N, 里面有M 个数字， N >> M
所以这个array大概是这样：
0011111222222333333333333.。。
现在要找出最长的连续重复subarray 比如333333333333， 有什么比较好的方法？ |
l****o
发帖数: 315 | 2 从头到尾count一遍。
O(n)的时间 O(1)的空间。 还可以优化吗？ |
h*****n
发帖数: 2872 | |
z*********8
发帖数: 2070 | 4 这个direction是对的， 具体怎么做？
【在 h*****n 的大作中提到】
: 可以考虑用二分法
|
l****o
发帖数: 315 | 5 恩，开始没看条件N>>M。
假设N个数被M等分。那么中间数应该是M[m/2]. 而这个数在N array里的位置应该是n/m
* m/2 - 1如果发现二分查找后找到的数字小于这个M[m/2]，说明更长串在左，否则在
右。依次类推。
【在 h*****n 的大作中提到】
: 可以考虑用二分法
|
z*********8
发帖数: 2070 | 6 等一下， 这个M个数不一定是连续的吧
/m
【在 l****o 的大作中提到】
: 恩，开始没看条件N>>M。
: 假设N个数被M等分。那么中间数应该是M[m/2]. 而这个数在N array里的位置应该是n/m
: * m/2 - 1如果发现二分查找后找到的数字小于这个M[m/2]，说明更长串在左，否则在
: 右。依次类推。
|
l****o
发帖数: 315 | 7 要么是连续的，要么条件告诉我包含了哪些数字的array。否则二分不make sense。
你想如果你都不知道有哪些数在里面，那从中间砍断（或者从其他位置），得到一个数
，那这个数能给你什么信息？
【在 z*********8 的大作中提到】
: 等一下， 这个M个数不一定是连续的吧
:
: /m
|
h*****n
发帖数: 2872 | 8 可以看中间这个数是不是和首尾两数相等
【在 l****o 的大作中提到】
: 要么是连续的，要么条件告诉我包含了哪些数字的array。否则二分不make sense。
: 你想如果你都不知道有哪些数在里面，那从中间砍断（或者从其他位置），得到一个数
: ，那这个数能给你什么信息？
|
l*n
发帖数: 529 | 9 假设只有0，1，2，3，其中0和2只有一个，2和3相同或者只差一个，这时候除了统计2
和3的具体个数你怎么能分出来到底是2多还是3多？所以必须计数，二分只是用来记数
的：从位置0开始，看剩下的中点是不是同一个数，不是就缩半，是就再跳一半。
【在 z*********8 的大作中提到】
: 这个direction是对的， 具体怎么做？
|
l****o
发帖数: 315 | 10 然后？
111129999 首尾相同吗？ 然后怎么样？
【在 h*****n 的大作中提到】
: 可以看中间这个数是不是和首尾两数相等
|
t*******0
发帖数: 16 | 11 可以将数组N 进行N/M等分，取N[0],N[N/m],N[2*N/M]....N[(M-1}*N/M)，N[N-1].多取
最后的一个数可以确保至少一个数重复一次。最大的连续数应该出现在重复次数最多的
那一个或几个数。如果只有一个，得到结果。多于一个则对这些数寻找左右边界。 |
a******e
发帖数: 710 | 12 先考虑只有两种元素的情况
00000000000000011111111111111111111111
要求找到最后一个0的index，这样就可以用binary search，复杂度是log n
现在考虑有M个数字：
1. 找到最后一个0的位置，复杂度logN, 同时知道了第一个1的位置
2. 找到最后一个1的位置，复杂度为log N，同时知道了第一个2的位置。
以此类推，总的复杂度为
O(M log N)
还有另外一种方法，思路也是找一个数字有多少个。
还以00000011111111111111111为例，
int end=1;
for (; end
if (v[end]!=0) break;
end = min(end, v.size()-1)
然后对v[0,end]间的元素做binary search找最后一个0的位置。
这个方法中，end<=2*(# of 0)
所以这种方法的复杂度为
O(M log Max_len)其中Max_len为最多的那个元素的个数。
当然两种方法worst case复杂度是一样的。
【在 z*********8 的大作中提到】
: 一个int array 长度为N, 里面有M 个数字， N >> M
: 所以这个array大概是这样：
: 0011111222222333333333333.。。
: 现在要找出最长的连续重复subarray 比如333333333333， 有什么比较好的方法？
|
h*****n
发帖数: 2872 | 13 不相同就继续往下分a
【在 l****o 的大作中提到】
: 然后？
: 111129999 首尾相同吗？ 然后怎么样？
|
