【面试经典150题】多数元素

🔗题目链接

✈题目描述：

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

⌊ n/2 ⌋表示n/2结果向下取整。

🚆数据范围：

• n == nums.length
• 1 <= n <= 5 * 104
• -109 <= nums[i] <= 109

🍁思路分析:

因为$\lfloor \frac{n}{2}\rfloor \le \frac{n}{2}<\lfloor \frac{n}{2}\rfloor +1$，所以这个 多数元素 至多只有1个。

🖊解法1：

使用一个辅助对象计数，遍历数组，如果有一个元素的次数超过了 ⌊ n/2 ⌋，即为结果。

/*** @param {number[]} nums* @return {number}*/
var majorityElement = function(nums) {let count={};let flag=Math.floor(nums.length/2);for(let i=0;i<nums.length;i++){if(count[nums[i]]===undefined){count[nums[i]]=0;}count[nums[i]]++;if(count[nums[i]]>flag){return nums[i];}}
};

时间复杂度：$O(n)$

空间复杂度：$O(n)$

🖊解法2：

由于多数元素的个数大于其他所有元素总和，所以我们可以从头维护一个候选元素，同时给其计数，遇到同类元素+1，遇到异类元素-1，减为0时，再维护当前元素，再重复之前步骤。

/*** @param {number[]} nums* @return {number}*/
var majorityElement = function(nums) {let candidate=nums[0];let count=1;for(let i=1;i<nums.length;i++){if(count===0){candidate=nums[i];count=1;}else if(candidate===nums[i]){count++;}else{count--;}}return candidate;
};

时间复杂度：$O(n)$

空间复杂度：$O(1)$