Find the repeated numbers in a sorted array using less than O(n) time complexity.

google的一道算法题,由@如何快速的找出重复的数?想起来问题,可以先参考下,题目不一样哦。
目的很明确,时间复杂度低于O(n),是否连续题目中没有说明,可以做两种方式考虑一下:
连续1,1,1,2,2,2,3,3,4,5,6,7,8,8,8
不连续1,1,3,4,5,9,10
So, if you have, A[] = {1,1,1,2,2,2,3,3,4}
you should print, 1=>3, 2=>3, 3=>2, 4=>1

Geo5
Geo5
463
编辑于2012-03-08
评论 (5)链接2012-03-08 
  • 0 支持
    个数都找出来了,重复的数当然就找出来了。。。 – 王辉 2012-03-08
  • 0 支持
    less than O(n)倒不难,难的是less than O(m),m是数组中包含的不重复数字个数。。。最常规的做法复杂度为O(m)*ln(k),k是数字最大重复次数,不漂亮。。。继续考虑 – 彭玮琳 2012-03-08
  • 0 支持
    先把你O(m)*ln(k)的写出来。 – 王辉 2012-03-09
  • 0 支持
    O(m + logn) – 灵剑2012 2012-09-11
显示更多隐藏的评论
  
map<int, int> blist;

void count_dup(int* arr, int start, int end)
{
if(end == 0)
blist[arr[start]]+=1;

if(start<end) {
if(arr[start] == arr[end]) {
blist[arr[end]] += end - start + 1;
return;
}

int mid = abs((start+end)/2);
if(end - start == 2 && arr[start] < arr[mid] && arr[mid] < arr[end]) {
blist[arr[start]] +=1;
blist[arr[mid]] +=1;
blist[arr[end]] +=1;
return;
}

if(arr[start] != arr[mid] && start == mid) {
blist[arr[start]]+=1;
blist[arr[mid]] += 1;
return;
}

if(arr[start] < arr[mid]) {
count_dup(arr, start, mid);
}
else {
blist[arr[mid]] += mid - start + 1;
}

if(arr[mid+1] != arr[end] && mid+1 == end) {
blist[arr[mid+1]]+=1;
blist[arr[end]] += 1;
return;
}


if(arr[mid+1] < arr[end]) {
count_dup(arr, mid+1, end);
}
else {
blist[arr[end]] += end - mid;
}
}
}

void main()
{
int A[] = {1,2,2,3,3,3,4,4,4,5,5,5,5,6,6,6,6,7,7,8,9};
count_dup(A, 0,20);

}
该答案已被锁定,无法对其进行评论,编辑及投票。
()
评论 (2)链接 • 2012-03-08
  • 0 支持
    其实我觉得写出来不难,难的是证明复杂度……比如怎么证明这个是O(m + logn)的复杂度 – 灵剑2012 2012-09-11
  • 0 支持
    可以不可以说算法思想啊,看别人写的无注释的代码太难受啦~ – 习惯挑战 2012-11-05

楼上的算法完全正确,并且复杂的是小于O(n)的,但是程序我还没有测试,毕竟分治法的边界条件判断是容易出错的。

我就说一下楼上的算法思想吧,我和他的第一反应是相同的,就是分治法。
显然给定了 sorted array, 分治就是最好的策略。

19个数字
1 1 1 2 2 4 4 4 4 6 6 6 7 10 10 10 10 10 12
先取第10个6。
左边递归
1 1 1 2 2 4 4 4 4
取第5个2。
左边递归
1 1 1 2
。。。。。。
接着递归右边
4 4 4 4
开头结尾相同直接 blist[4] += 4。 注意这里,有了这项优化复杂度已经小于O(n)了。
右边递归
6 6 7 10 10 10 10 10 12
。。。。。。

显然这种算法复杂度是 Less than O(n) 的。因为如果统计个数n次,那么 blist 需要 n次+1,然而在递归的过程中如果有 收尾相同就直接跳过了,所以复杂度小于O(n)。

当然楼上如果把代码改为非递归程序会更快。

该答案已被锁定,无法对其进行评论,编辑及投票。
()
评论 (0)链接 • 2013-07-25
德问是一个专业的编程问答社区,请 登录注册 后再提交答案