多数元素
排序
-
解题思路：
- 排序数组，如果有一个数字出现的频率大于 n/2，则在数组 nums.length / 2 的位置就是这个数；
-
复杂度：
- 时间复杂度：O(nlogn)，快排的时间复杂度；
- 空间复杂度：O(logn)，排序需要 logn 的空间复杂度；
-
代码实现：
var majorityElement = function (nums) { nums.sort((a, b) => a - b); return nums[Math.floor(nums.length / 2)]; };
哈希
-
解题思路：
- 循环数组，用哈希表存储数字和对应的个数，如果数字出现的个数大于 n/2 则返回这个数；
-
复杂度：
- 时间复杂度：O(n)，n 为 nums 数组的长度；
- 空间复杂度：O(n），哈希表需要的空间；
-
代码实现：
var majorityElement = function (nums) { let half = nums.length / 2; let map = new Map; for (let num of nums) { if (map.has(num)) { let currNum = map.get(num); map.set(num, currNum + 1); } else { map.set(num, 1); } if (map.get(num) > half) return num; } };
摩尔投票法
-
解题思路：
- 维护一个候选众数 candidate 和它出现的次数 count，初始时 candidate 可以为任意值，count 为 0；
- 遍历数组 nums 中的所有元素，对于每个元素 x，在判断 x 之前，如果 count 的值为 0，先将 x 的值赋予 candidate，随后判断 x：
- 如果 x 与 candidate 相等，那么计数器 count 的值增加 1；
- 如果 x 与 candidate 不等，那么计数器 count 的值减少 1，当减少为 0 时，将下一个数赋予 candidate；
- 在遍历完成后，candidate 即为整个数组的众数；
-
复杂度：
- 时间复杂度：O(n)，只对数组进行了一次遍历；
- 空间复杂度：O(1)，只需要常数级别的额外空间；
-
代码实现：
const majorityElement = nums => { let count = 1; // 将第一个数赋予 majority let majority = nums[0]; for (let i = 1; i < nums.length; i++) { if (count === 0) { majority = nums[i]; } if (nums[i] === majority) { count++; } else { count--; } } return majority; };
分治
-
解题思路：
- 使用经典的分治算法递归求解，直到所有的子问题都是长度为 1 的数组；
- 长度为 1 的子数组中唯一的数显然是众数，直接返回即可；如果回溯后某区间的长度大于 1，必须将左右子区间的值合并；如果它们的众数相同，那么显然这一段区间的众数是它们相同的值；否则，需要比较两个众数在整个区间内出现的次数来决定该区间的众数；
-
复杂度：
- 时间复杂度：O(nlogn)；
- 空间复杂度：O(logn)；尽管分治算法没有直接分配额外的数组空间，但在递归的过程中使用了额外的栈空间；算法每次将数组从中间分成两部分，所以数组长度变为 1 之前需要进行O(logn) 次递归，即空间复杂度为 O(logn)；
-
代码实现：
var majorityElement = function (nums) { const getMode = (low, high) => { if (low === high) return nums[low]; //拆分成更小的区间，一分为二 let mid = Math.floor((low + high) / 2); let left = getMode(low, mid); let right = getMode(mid + 1, high); if (left === right) return left; let leftCount = getCount(left, low, high);// 统计区间内 left 的个数 let rightCount = getCount(right, low, high);// 统计区间内 right 的个数 return leftCount > rightCount ? left : right;// 返回 left 和 right 中个数多的那个 }; //统计 low 到 high 之间 num 的数量 var getCount = (num, low, high) => { let count = 0; for (let i = low; i <= high; i++) { if (nums[i] === num) count++; } return count; }; return getMode(0, nums.length - 1); };
打赏作者
您的打赏是我前进的动力
微信
支付宝
面试题 10.09.排序矩阵查找
上一篇
评论
