05-多数元素

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

 ⌊ n/2 ⌋ 的元素。

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

方法一：哈希表法

通过哈希表来记录每个元素出现的次数，然后找出出现次数大于 ⌊ n/2 ⌋ 的元素。

function majorityElement(nums: number[]): number {const numCount: Record<number, number> = {};const n = nums.length;for (const num of nums) {if (num in numCount) {numCount[num]++;} else {numCount[num] = 1;}if (numCount[num] > Math.floor(n / 2)) {return num;}}return -1; // 理论上不会执行到这里，因为题目保证存在多数元素
}

复杂度分析

• 时间复杂度：(O(n))，因为只需要对数组进行一次遍历。
• 空间复杂度：(O(k))，其中 (k) 是数组中不同元素的数量，最坏情况下 (k = n)。

方法二：排序法

由于多数元素出现的次数大于 ⌊ n/2 ⌋，那么排序后数组中间位置的元素一定是多数元素。

function majorityElement(nums: number[]): number {nums.sort((a, b) => a - b);return nums[Math.floor(nums.length / 2)];
}

复杂度分析

• 时间复 O(n log n))，主要是排序操作的时间复杂度。
• 空间复杂度：取决于排序算法的实现，一般为 (O(log n))。

方法三：摩尔投票法

这是一种非常高效的算法，它的核心思想是抵消不同元素，最后剩下的元素就是多数元素。

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

复杂度分析

• 时间复杂度：(O(n))，只需要对数组进行一次遍历。
• 空间复杂度：(O(1))，只使用了常数级的额外空间。

测试代码示例 

const nums = [2, 2, 1, 1, 1, 2, 2];
const result = majorityElement(nums);
console.log("多数元素是:", result);

 在上述三种方法中，摩尔投票法在时间和空间复杂度上表现最优，推荐使用该方法来解决此问题。