你将得到一个长度不超过 232 的 32 位无符号整数数组,且数组中有超过一半的元素都相等于一个 32 位无符号整数 N。请找出 N,只遍历数组中的每个数字一次,并使用不超过 2 kB 的内存。
你的解决方案必须是确定性的,并保证能够找到 N。
你将得到一个长度不超过 232 的 32 位无符号整数数组,且数组中有超过一半的元素都相等于一个 32 位无符号整数 N。请找出 N,只遍历数组中的每个数字一次,并使用不超过 2 kB 的内存。
你的解决方案必须是确定性的,并保证能够找到 N。
为每个位保留一个整数,并适当地为数组中的每个整数递增此集合。
最后,某些位的计数将高于数组长度的一半 - 这些位确定了N。当然,计数将高于N出现的次数,但这并不重要。重要的是,任何不属于N的位不能出现超过一半的次数(因为N具有超过一半的条目),而任何属于N的位必须出现超过一半的次数(因为它将在每次N出现时出现,并且可能有额外出现)。
(目前没有代码 - 即将失去网络访问权限。希望上述内容足够清晰。)
Boyer 和 Moore 的 “线性时间多数投票算法” - 在遍历数组时保持您对答案的当前猜测。
public uint MostCommon(UInt32[] numberList)
{
uint suspect = 0;
int suspicionStrength = -1;
foreach (uint number in numberList)
{
if (number==suspect)
{
suspicionStrength++;
}
else
{
suspicionStrength--;
}
if (suspicionStrength<=0)
{
suspect = number;
}
}
return suspect;
}
注意:我没有测试过这段代码,请自行决定是否使用。
Jon算法的伪代码(记事本C++ :-)):
int lNumbers = (size_of(arrNumbers)/size_of(arrNumbers[0]);
for (int i = 0; i < lNumbers; i++)
for (int bi = 0; bi < 32; bi++)
arrBits[i] = arrBits[i] + (arrNumbers[i] & (1 << bi)) == (1 << bi) ? 1 : 0;
int N = 0;
for (int bc = 0; bc < 32; bc++)
if (arrBits[bc] > lNumbers/2)
N = N | (1 << bc);
a0, a1, . . . , an−1
包含一个领导者,则在删除两个不同值的元素后,剩余序列仍具有相同的领导者。事实上,如果我们删除两个不同的元素,则只有其中一个可能是领导者。新序列中的领导者出现次数大于 n/2 − 1
= (n−2)/2
次。因此,它仍然是具有 n − 2
个元素的新序列的领导者。def goldenLeader(A):
n = len(A)
size = 0
for k in xrange(n):
if (size == 0):
size += 1
value = A[k]
else:
if (value != A[k]):
size -= 1
else:
size += 1
candidate = -1
if (size > 0):
candidate = value
leader = -1
count = 0
for k in xrange(n):
if (A[k] == candidate):
count += 1
if (count > n // 2):
leader = candidate
return leader
def majority_element(arr):
counter, possible_element = 0, None
for i in arr:
if counter == 0:
possible_element, counter = i, 1
elif i == possible_element:
counter += 1
else:
counter -= 1
return possible_element
O(n)
,其中常数非常小(比如 3)。此外,它的空间复杂度似乎是 O(1)
,因为我们只初始化了三个变量。问题在于,这些变量中有一个是计数器,其可能会增长到 n
(当数组由相同的数字组成时)。而要存储数字 n
,需要 O(log (n))
的空间。因此,从理论上讲,它的时间复杂度为 O(n)
,空间复杂度为 O(log(n))
。从实际角度来看,longint 可以容纳 2^128 个数字,而数组中的元素数量是不可想象的巨大。我对这个算法有些记忆,它可能遵循2K规则,也可能不遵循。为了避免由于函数调用而破坏内存限制,可能需要使用堆栈等方式进行重写,但这可能是不必要的,因为它只有对数数量的这种调用。无论如何,我在大学时或者说有一个涉及分治的递归解决方案,其中的秘密是当你将组分成两半时,至少有一半仍然有超过一半的值等于最大值。在分割时的基本规则是返回两个候选的顶部值,其中一个是顶部值,另一个是其他值(可能是第二名,也可能不是)。我忘记了算法本身。
针对buti-oxa / Jason Hernandez的答案,假设Jason的答案与buti-oxa的答案相同,并且两者都按照算法描述的方式工作,我们需要证明其正确性:
我们将调整后的怀疑强度定义为:如果选择了最高值,则等于怀疑强度;如果没有选择最高值,则为-怀疑强度。每次选择正确的数字时,当前的调整后怀疑强度增加1。每次选择错误的数字时,它要么减少1,要么增加1,具体取决于当前是否选择了错误的数字。因此,最小可能的结束时调整后怀疑强度等于number-of[top values] - number-of[other values]。