Loading... 如何高效地获得一段序列的众数? 我们可以使用 `摩尔投票算法`。 这个算法的基本思想是利用一个变量c来记录候选的主元素,以及一个计数器count来记录c出现的次数。初始时,c为第一个元素,count为1。然后从第二个元素开始遍历数组,如果当前元素等于c,就将count加1;如果不等于c,就将count减1。当count减到0时,说明c已经不是出现次数最多的元素,需要更新c为当前元素,并将count重置为1。这样一直遍历到数组末尾,最后的c就是出现次数最多的元素。 这个算法之所以能找到出现次数最多的元素,是因为如果一个元素出现的次数超过了数组长度的一半,那么它与其他不同的元素相互抵消后,最后一定会剩下至少一个。而如果没有这样的元素,那么最后的c可能是任意一个元素,所以还需要再次遍历数组来验证它的出现次数是否真的最多。 时间复杂度 O(n),空间复杂度 O(1)。 为了严谨地证明这个算法的正确性,我们可以使用数学归纳法。假设数组的长度为n,我们要证明对于任意的n,算法都能找到出现次数最多的元素(如果存在)。 * 基础情况:当n=1时,算法显然正确,因为只有一个元素,它就是出现次数最多的元素。 * 归纳步骤:假设当n=k时,算法正确,即能找到出现次数最多的元素(如果存在)。那么当n=k+1时,算法也正确。我们分两种情况讨论: * 如果数组中没有出现次数超过一半的元素,那么算法最后得到的c可能是任意一个元素,但是它不是出现次数最多的元素。这时,我们需要再次遍历数组来验证c的出现次数是否真的最多。如果是,那么算法正确;如果不是,那么算法会返回没有这样的元素,也是正确的。 * 如果数组中有出现次数超过一半的元素x,那么算法最后得到的c一定是x。这是因为x与其他不同的元素相互抵消后,最后一定会剩下至少一个x。而且,在抵消过程中,c可能会被更新为其他元素,但是每次更新后,count都会重置为1。而x每次出现时,count都会加1。所以,在遍历完数组后,count一定大于0,并且c一定等于x。 因此,无论哪种情况,算法都能找到出现次数最多的元素(如果存在)。根据数学归纳法,算法对于任意长度的数组都正确。这就证明了这个算法的正确性。 最后修改:2023 年 09 月 23 日 © 允许规范转载 赞 如果觉得我的文章对你有用,请随意赞赏