130 lines
3.4 KiB
JavaScript
130 lines
3.4 KiB
JavaScript
/*
|
||
169. 多数元素
|
||
已解答
|
||
简单
|
||
|
||
相关标签
|
||
相关企业
|
||
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
|
||
|
||
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
|
||
|
||
示例 1：
|
||
|
||
输入：nums = [3,2,3]
|
||
输出：3
|
||
示例 2：
|
||
|
||
输入：nums = [2,2,1,1,1,2,2]
|
||
输出：2
|
||
|
||
提示：
|
||
n == nums.length
|
||
1 <= n <= 5 * 104
|
||
-109 <= nums[i] <= 109
|
||
|
||
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
|
||
*/
|
||
|
||
// 思路1: 排序，在取1/2
|
||
// /**
|
||
// * @param {number[]} nums
|
||
// * @return {number}
|
||
// */
|
||
// var majorityElement = function(nums) {
|
||
// nums.sort((a,b)=>a-b)
|
||
// return nums[nums.length>>1]
|
||
// };
|
||
|
||
// 思路2: 遍历整个数组，每一项作为key存入map中，value为出现的次数，最后遍历map，找到最大值
|
||
// /**
|
||
// * @param {number[]} nums
|
||
// * @return {number}
|
||
// */
|
||
// const majorityElement = function (nums) {
|
||
// const len = nums.length;
|
||
// const map = new Map();
|
||
// for (let i = 0; i < len; i++) {
|
||
// map.set(nums[i], (map.get(nums[i]) || 0) + 1);
|
||
// }
|
||
// // 遍历map
|
||
// let result;
|
||
// let maxValue = -Infinity;
|
||
// for (const [key, value] of map.entries()) {
|
||
// if (value > maxValue) {
|
||
// maxValue = value;
|
||
// result = key;
|
||
// }
|
||
// }
|
||
// return result;
|
||
// };
|
||
|
||
// 思路4: 如果数 a 是数组 nums 的众数，如果我们将 nums 分成两部分，那么 a 必定是至少一部分的众数。
|
||
// /**
|
||
// * @param {number[]} nums
|
||
// * @return {number}
|
||
// */
|
||
// function majorityElement(nums) {
|
||
// // 递归函数
|
||
// function majorityElementRec(lo, hi) {
|
||
// // 基本情况：子数组长度为1时，返回该元素
|
||
// if (lo === hi) {
|
||
// return nums[lo];
|
||
// }
|
||
|
||
// // 分割数组
|
||
// const mid = Math.floor((hi - lo) / 2) + lo;
|
||
// const leftMajority = majorityElementRec(lo, mid);
|
||
// const rightMajority = majorityElementRec(mid + 1, hi);
|
||
|
||
// // 如果左右两半的多数元素相同，直接返回
|
||
// if (leftMajority === rightMajority) {
|
||
// return leftMajority;
|
||
// }
|
||
|
||
// // 统计左右多数元素的出现次数
|
||
// const leftCount = countInRange(nums, leftMajority, lo, hi);
|
||
// const rightCount = countInRange(nums, rightMajority, lo, hi);
|
||
|
||
// // 返回出现次数较多的元素
|
||
// return leftCount > rightCount ? leftMajority : rightMajority;
|
||
// }
|
||
|
||
// // 辅助函数：统计元素在范围内的出现次数
|
||
// function countInRange(nums, num, lo, hi) {
|
||
// let count = 0;
|
||
// for (let i = lo; i <= hi; i++) {
|
||
// if (nums[i] === num) {
|
||
// count++;
|
||
// }
|
||
// }
|
||
// return count;
|
||
// }
|
||
|
||
// // 调用递归函数，初始范围为整个数组
|
||
// return majorityElementRec(0, nums.length - 1);
|
||
// }
|
||
|
||
// 思路4: 按照选举的思想，赢得选票的肯定是多数的
|
||
|
||
function majorityElement(nums) {
|
||
let candidate = null; // 表示当前赢得选票的候选人
|
||
let count = 0; // 表示当前候选人的票数
|
||
const len = nums.length;
|
||
|
||
for (let i = 0; i < len; i++) {
|
||
if (count === 0) {
|
||
candidate = nums[i]; // 更换候选人
|
||
count = 1;
|
||
} else if (nums[i] === candidate) { // 票数增加
|
||
count++;
|
||
} else { // 票数减少
|
||
count--;
|
||
}
|
||
}
|
||
|
||
return candidate;
|
||
}
|
||
|
||
console.log(majorityElement([12, 2, 3, 1, 1, 1, 1]));
|