算法题记录——多数元素

原题：给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

示例 ：

输入：nums = [2,2,1,1,1,2,2]
输出：2

思路一

首先想到用哈希表记录每个元素出现的次数，然后遍历哈希表，次数最多的值即为答案，比较简单，在此就不放代码了

复杂度：需要遍历一次数组，一次哈希表，且需要哈希表存储最多 n/2 + 1 个元素，故时间复杂度O(n)，空间复杂度O(n)

思路二

上面的思路不满足题目进阶要求中的空间复杂度O(1)，仔细想想自己忽略了一个条件——多数元素出现次数大于 n/2。

要利用这个条件需要一个数学公式，令数组总长度为a，多数元素个数为b，在题目所给条件下有(证明在下方)：

 \frac{b}{a} > \frac{1}{2}，\frac{b - 1}{a - 2} > \frac{1}{2}

考虑每次从数组中取出两个不同的元素，由于多数元素出现次数大于 n/2，由上面的公式可知，在最坏情况，即每次都取出多数元素的情况下，取出两个不同元素后，数组的多数元素仍然不变

故可将上述思路转换为：将第一个元素设为候选多数元素，遍历数组并计数，若遇到不同元素，则将当前元素的计数减一(相当于取出两个不同元素)，反之加一，元素的计数为0时将候选元素替换为下一个元素，最终剩下的候选元素即为我们需要的结果

代码：

var majorityElement = function(nums) {
    let res, t = 0
    for(let i = 0; i < nums.length; ++i) {
        if (t === 0) { res = nums[i] }
        nums[i] === res ? ++t : --t
    }
    return res
};

复杂度：需要遍历一次数组，两个变量分别储存候选元素、元素计数器，故时间复杂度O(n)，空间复杂度O(1)

证明

若 a,b,m,n > 0，a > b，m > n，\frac{b}{a} > \frac{n}{m}(b > n，a > m)，则 \frac{b - n}{a - m} > \frac{n}{m}

证：

\frac{b - n}{a - m} = \frac{b}{a}(\frac{1-\frac{n}{b}}{1-\frac{m}{a}})\\

令 b = \beta a，则\\
\frac{b - n}{a - m} = \frac{b}{a}(\frac{1-\frac{n}{\beta a}}{1-\frac{m}{a}})，且由\frac{b}{a} > \frac{n}{m} 可知 \beta > \frac{n}{m}\\
故 \frac{n}{\beta} < m，\frac{n}{\beta a} < \frac{m}{a}，\frac{1-\frac{n}{\beta a}}{1-\frac{m}{a}} > 1\\
故\frac{b - n}{a - m} > \frac{b}{a} > \frac{n}{m}