题目链接https://leetcode.cn/problems/majority-element/官解题方链接https://leetcode.cn/problems/majority-element/solutions/146074/duo-shu-yuan-su-by-leetcode-solution/前言昨天还在“双指针”里绕圈今天就要“以一敌百”今天是算法训练营的第十二天。题目定义很明确给一个大小为n的数组找出那个出现次数 大于⌊n/2⌋的元素。而且题目保证了一定存在这个元素。我第一反应是这不就是数数吗谁多选谁。于是上了哈希表。结果发现这道题的解法简直五花八门从排序到随机化最后那个“摩尔投票法”更是让我直呼内行。下面是我的探索记录。一、 第一次尝试哈希表计数法最直观的思路就是遍历数组用哈希表记录每个数字出现的次数一旦某个数字的次数超过n/2直接返回。代码实现#include uthash.hstruct hashTable {int key;int val;UT_hash_handle hh;};int majorityElement(int* nums, int numsSize) {struct hashTable* map NULL;int threshold numsSize / 2;for (int i 0; i numsSize; i) {struct hashTable* tmp;HASH_FIND_INT(map, nums[i], tmp);if (tmp NULL) {// 第一次遇到这个数tmp (struct hashTable*)malloc(sizeof(struct hashTable));tmp-key nums[i];tmp-val 1;HASH_ADD_INT(map, key, tmp);} else {// 遇到过计数加一tmp-val;}// 检查是否超过阈值if (tmp-val threshold) {return nums[i];}}return 0;}遇到的问题空间复杂度这种方法需要额外的哈希表空间空间复杂度是 O(n)虽然能过但不够优雅。C语言环境还是老生常谈的问题本地调试得配uthash.h提交时记得删掉main函数。二、 第二次尝试排序取中位数既然题目说这个元素出现次数超过了一半那如果我们把数组排个序中间那个位置下标 n/2一定是这个多数元素。比如[2, 2, 1, 1, 1, 2, 2]排序后是[1, 1, 1, 2, 2, 2, 2]。长度是 7中间下标是 3nums[3]刚好是 2。代码实现// qsort 比较函数int cmp(const void* a, const void* b) {return *(int*)a - *(int*)b;}int majorityElement(int* nums, int numsSize) {// 直接排序qsort(nums, numsSize, sizeof(int), cmp);// 返回中间位置的元素return nums[numsSize / 2];}分析这种方法代码量最少但时间复杂度取决于排序算法通常是 O(nlog⁡n)。比哈希表快一点但还不是最优解。三、 进阶尝试摩尔投票法这是这道题的最优解也是最难理解的地方。核心逻辑我们可以把“多数元素”看作 1“非多数元素”看作 -1。因为多数元素的数量超过了一半所以把它们全部加起来结果一定是正数。我们维护一个“候选人”和“票数”。遇到相同的数票数 1。遇到不同的数票数 -1。如果票数归零换一个新的候选人。为什么这样是对的因为多数元素的数量比其他所有元素加起来还多。就算其他元素全部联合起来跟多数元素“同归于尽”票数抵消最后剩下的那个候选人一定还是多数元素。代码实现int majorityElement(int* nums, int numsSize) {int candidate nums[0];int count 1;for (int i 1; i numsSize; i) {if (count 0) {// 票数归零换人坐庄candidate nums[i];count 1;} else if (nums[i] candidate) {// 遇到队友票数加一count;} else {// 遇到敌人票数减一count--;}}return candidate;}四、 总结今天这道题让我见识到了算法的多样性。暴力法哈希表最直观但费空间。排序法利用题目特性超过一半代码极简但费时间。摩尔投票法真正的“算法之美”时间和空间都最优。