tib*_*ama 3 c++ arrays programming-languages
有一个n个数字的数组.一个数字重复n/2次,其他n/2个数字不同.找到重复的数字.(最佳soln是o(n)正好n/2 + 1比较.)
这里的主要问题是n/2 + 1比较.我有两个O(n)的解决方案,但他们正在进行超过n/2 + 1的比较.
1>将数组的数量除以三个组.比较任何相同元素的n/3组.例如,数组是(1 10 3)(4 8 1)(11)....因此所需的比较数是7,即> n/2 + 1,即8/2 + 1 = 5
2>比较a [i]和[i + 1]和[i + 2]例如阵列是8 10 3 4 1 1 1 1
总共9次比较
我甚至感激一点帮助.谢谢
空间复杂度为O(1).
Luk*_*hne 10
当然,如果所有其他都不同,你只需比较所有对.如果你找到一对两个相同的数字,你就有了这个数字
假设你有这样的数字(它只是关于索引)
[1,2,3,4,5,6,7,8,9,10]
然后你做这样的n/2 + 1比较
(1,2),(3,4),(5,6),(7,8),(9,7),(9,8)
如果所有对都不同,则返回10.
那么当你比较最后4个剩余的数字(7,8,9,10)时,你知道其中至少有两个相同的数字并且你有3个比较.