找到重复超过n/2次的元素

Question

存在具有重复超过N/2个时间的元素的阵列(大小为N),并且阵列中的其余元素也可以重复,但是仅重复一个元素超过N/2次.找到号码.

我可以想到几种方法:

• 天真,保持哈希映射中每个数字的计数.
• 最简单的是,排序数组和n/2 + 1索引处的数字是所需的数字.
• 保持仅查找连续重复值的计数.单独检查交替存储值的模式.

无法想到更好的解决方案,必须有.

Answer 1

有一个很好的算法来解决这个问题,它只使用恒定的外部空间(O(1))两次通过(总时间O(N)).我有这个算法的实现,以及包含正确性证明的注释,可在此处获得

算法背后的直觉实际上非常漂亮.假设你有一个满屋子的人,每个人都拿着一个阵列元素.每当两个人发现彼此都没有拿着与另一个相同的数组元素时,他们两个坐下.最终,在最后,如果有人站着,他们有可能占多数,你可以检查那个元素.只要一个元素出现频率至少为N/2,就可以保证这种方法总能找到多数元素.

要实际实现该算法,您需要对数组进行线性扫描,并跟踪当前关于多数元素是什么的猜测,以及到目前为止您看到它的次数.最初,此猜测未定义且重复次数为零.当您遍历数组时,如果当前元素与您的猜测匹配,则递增计数器.如果当前元素与您的猜测不匹配,则递减计数器.如果计数器达到零,则将其重置为您遇到的下一个元素.您可以将此实现视为上述"站在房间里"算法的具体实现.每当两个人遇到不同的元素时,他们就会取消(丢掉柜台).每当两个人拥有相同的元素时,他们就不会互相交流.

有关完整的正确性证明,引用原始论文(Boyer和Moore的更着名的Boyer-Moore字符串匹配算法)以及C++中的实现,请查看上面的链接.

Answer 2

这是多数元素问题.对于这个问题,存在单程,恒定空间算法.这是一个用python编写的简短算法:

    import random

    items = [1, 2, 3, 4, 5, 5, 5, 5, 5 ]
    # shuffle the items
    random.shuffle(items)

    print("shuffled items: ", items)

    majority_elem = items[0]
    count = 1
    for i in range(1,len(items)):
        if items[i] == majority_elem:
            count += 1
        else: 
            count -= 1
            if count == 0:
                majority_elem = items[i]
                count = 1

    print("majority element : %d" % majority_elem )

  

我们使用变量majority_elem来跟踪多数元素和计数器(计数)

• 最初,我们将数组的第一个元素设置为多数元素.

• 我们浏览阵列,

• 如果当前元素==多数元素:增量计数

• 否则:{减量计数.如果count变为零,则设置count = 1并设置majority_element = current元素.}

这个问题有一个变化,而不是数组,可能会有一个非常大的序列,我们不知道手头的长度.如果是这种情况,排序或分区是没有用的.

参考文献:

• 计算机编程的艺术,分册0:组合算法和布尔函数的介绍,第0卷; 第4卷

Answer 3

无需排序。您可以简单地使用中值选择算法来确定第 n/2 个元素。快速选择在 O(n) 预期时间内运行。中位数的中位数运行时间为 O(n)。

Answer 4

如果一个元素重复超过N/2次,那么它必须是中位数.有许多算法可以让您有效地找到它.

Answer 5

你熟悉quicksort吗？它有一个名为'partition'的函数,给定一个值,将数组划分为一个区域,其中所有值都大于值(pivot)在一侧,而小于该值的所有值都在另一侧.请注意,这不是一种排序,只是一种分离.N/2计数项目将在两个部分中较大的一部分.您可以递归地应用此技术在O(n)时间内查找元素.

维基百科:快速排序,或基于分区的一般选择算法

Answer 6

在第二种方法中,您基本上是选择中值元素.查看用于查找数字列表中位数的算法.特别是,选择算法可以正常工作并在O(n)中计算它.

Hoare的选择算法与快速排序非常相似,只是它不是递归两个分区,而是只递归一个分区(包含第k个元素的分区).

在C++中,标准库以形式提供选择算法std::nth_element,保证O(n)平均复杂度.你可以用这个找到中位数.

int a[8] = {5, 1, 1, 1, 2, 1, 3, 1};
int median = *std::nth_element(a, a + 4, a + 8);

请注意,std::nth_element这也将对数组进行部分排序.