Spa*_*dan 7 arrays algorithm complexity-theory
来源:微软访谈问题
给定一个排序数组,其中每个元素出现两次,除了一次出现的单元,我们需要找到该元素.
现在标准的O(n)解决方案是执行列表的异或,它将返回未重复的元素(因为所有重复的元素都会被取消).
如果我们知道数组已经排序,是否有可能更快地解决这个问题？
Dan*_*her 14
是的,您可以使用排序来O(log n)通过二进制搜索来降低复杂性.
由于数组是在缺失元素之前进行排序的,因此每个值占据了斑点2*k和2*k+1数组(假设基于0的索引).
所以你去数组的中间,比如说索引h,检查索引h+1是否h为偶数,或者h-1是否h为奇数.如果缺少的元素稍后出现,则这些位置的值相等,如果之前的值,则值不同.重复,直到找到缺少的元素.