尧图网站建设 
题目描述给定一个大小为n的数组nums返回其中的多数元素。多数元素是指在数组中出现次数大于⌊ n/2 ⌋的元素。你可以假设数组是非空的并且给定的数组总是存在多数元素。示例 1输入nums [3,2,3]输出3示例 2输入nums [2,2,1,1,1,2,2]输出2解题思路方法一Boyer-Moore 投票算法(最优解)核心思路把多数元素看作正票其他元素看作负票。多数元素出现次数 n/2所以正票总数 负票总数。算法维护一个candidate和count遍历数组如果count 0把当前元素设为candidatecount 1如果当前元素 candidatecount否则count--最后candidate就是多数元素核心直觉多数元素的数量比其他所有元素加起来还多所以两两抵消后剩下的一定是多数元素。具体过程示例nums [2, 2, 1, 1, 1, 2, 2]inums[i]candidatecount说明0221count0设 candidate21222相同count2121不同count--3120不同count--4111count0设 candidate15210不同count--6221count0设 candidate2结果2✅代码实现class Solution { public: int majorityElement(vectorint nums) { int candidate 0; int count 0; for (int num : nums) { if (count 0) { candidate num; count 1; } else if (num candidate) { count; } else { count--; } } return candidate; } };更简洁的写法class Solution { public: int majorityElement(vectorint nums) { int candidate 0, count 0; for (int num : nums) { if (count 0) candidate num; count (num candidate) ? 1 : -1; } return candidate; } };复杂度分析维度复杂度说明时间复杂度O(n)一次遍历空间复杂度O(1)只用两个变量关键细节1. 为什么投票算法能工作核心证明设多数元素为m出现次数为c其他元素总数为n - c因为c n/2所以c n - c每次抵消一对不同的元素最多抵消n - c对剩下c - (n - c) 0个m所以最后的candidate一定是m2. 为什么不需要验证candidate题目保证一定存在多数元素所以投票算法的结果一定是正确的。如果题目不保证存在多数元素就需要再遍历一次验证candidate的出现次数是否 n/2。3. 和「求众数 II」的区别题目区别169. 多数元素出现次数 n/2最多一个229. 求众数 II出现次数 n/3最多两个229 题需要用两个候选人和两个计数器。方法二哈希表O(n) 空间代码实现class Solution { public: int majorityElement(vectorint nums) { unordered_mapint, int count; int n nums.size(); for (int num : nums) { if (count[num] n / 2) { return num; } } return -1; } };复杂度时间 O(n)空间 O(n)方法三排序O(n log n)代码实现class Solution { public: int majorityElement(vectorint nums) { sort(nums.begin(), nums.end()); return nums[nums.size() / 2]; } };原理排序后多数元素一定在中间位置。复杂度时间 O(n log n)空间 O(1)或 O(log n) 递归栈方法四分治O(n log n)代码实现class Solution { public: int majorityElement(vectorint nums) { return divide(nums, 0, nums.size() - 1); } private: int divide(vectorint nums, int left, int right) { if (left right) return nums[left]; int mid left (right - left) / 2; int leftMajor divide(nums, left, mid); int rightMajor divide(nums, mid 1, right); if (leftMajor rightMajor) return leftMajor; int leftCount countInRange(nums, leftMajor, left, right); int rightCount countInRange(nums, rightMajor, left, right); return (leftCount rightCount) ? leftMajor : rightMajor; } int countInRange(vectorint nums, int target, int left, int right) { int count 0; for (int i left; i right; i) { if (nums[i] target) count; } return count; } };复杂度时间 O(n log n)空间 O(log n)四种方法对比方法时间复杂度空间复杂度推荐度Boyer-Moore 投票O(n)O(1)⭐⭐⭐⭐⭐哈希表O(n)O(n)⭐⭐⭐⭐排序O(n log n)O(1)⭐⭐⭐分治O(n log n)O(log n)⭐⭐⭐总结要点说明核心思想投票算法多数元素正票多于负票关键操作count 0时换候选人相同加一不同减一时间复杂度O(n)空间复杂度O(1) 【分治-1】169.多数元素
题目描述给定一个大小为n的数组nums返回其中的多数元素。多数元素是指在数组中出现次数大于⌊ n/2 ⌋的元素。你可以假设数组是非空的并且给定的数组总是存在多数元素。示例 1输入nums [3,2,3]输出3示例 2输入nums [2,2,1,1,1,2,2]输出2解题思路方法一Boyer-Moore 投票算法(最优解)核心思路把多数元素看作正票其他元素看作负票。多数元素出现次数 n/2所以正票总数 负票总数。算法维护一个candidate和count遍历数组如果count 0把当前元素设为candidatecount 1如果当前元素 candidatecount否则count--最后candidate就是多数元素核心直觉多数元素的数量比其他所有元素加起来还多所以两两抵消后剩下的一定是多数元素。具体过程示例nums [2, 2, 1, 1, 1, 2, 2]inums[i]candidatecount说明0221count0设 candidate21222相同count2121不同count--3120不同count--4111count0设 candidate15210不同count--6221count0设 candidate2结果2✅代码实现class Solution { public: int majorityElement(vectorint nums) { int candidate 0; int count 0; for (int num : nums) { if (count 0) { candidate num; count 1; } else if (num candidate) { count; } else { count--; } } return candidate; } };更简洁的写法class Solution { public: int majorityElement(vectorint nums) { int candidate 0, count 0; for (int num : nums) { if (count 0) candidate num; count (num candidate) ? 1 : -1; } return candidate; } };复杂度分析维度复杂度说明时间复杂度O(n)一次遍历空间复杂度O(1)只用两个变量关键细节1. 为什么投票算法能工作核心证明设多数元素为m出现次数为c其他元素总数为n - c因为c n/2所以c n - c每次抵消一对不同的元素最多抵消n - c对剩下c - (n - c) 0个m所以最后的candidate一定是m2. 为什么不需要验证candidate题目保证一定存在多数元素所以投票算法的结果一定是正确的。如果题目不保证存在多数元素就需要再遍历一次验证candidate的出现次数是否 n/2。3. 和「求众数 II」的区别题目区别169. 多数元素出现次数 n/2最多一个229. 求众数 II出现次数 n/3最多两个229 题需要用两个候选人和两个计数器。方法二哈希表O(n) 空间代码实现class Solution { public: int majorityElement(vectorint nums) { unordered_mapint, int count; int n nums.size(); for (int num : nums) { if (count[num] n / 2) { return num; } } return -1; } };复杂度时间 O(n)空间 O(n)方法三排序O(n log n)代码实现class Solution { public: int majorityElement(vectorint nums) { sort(nums.begin(), nums.end()); return nums[nums.size() / 2]; } };原理排序后多数元素一定在中间位置。复杂度时间 O(n log n)空间 O(1)或 O(log n) 递归栈方法四分治O(n log n)代码实现class Solution { public: int majorityElement(vectorint nums) { return divide(nums, 0, nums.size() - 1); } private: int divide(vectorint nums, int left, int right) { if (left right) return nums[left]; int mid left (right - left) / 2; int leftMajor divide(nums, left, mid); int rightMajor divide(nums, mid 1, right); if (leftMajor rightMajor) return leftMajor; int leftCount countInRange(nums, leftMajor, left, right); int rightCount countInRange(nums, rightMajor, left, right); return (leftCount rightCount) ? leftMajor : rightMajor; } int countInRange(vectorint nums, int target, int left, int right) { int count 0; for (int i left; i right; i) { if (nums[i] target) count; } return count; } };复杂度时间 O(n log n)空间 O(log n)四种方法对比方法时间复杂度空间复杂度推荐度Boyer-Moore 投票O(n)O(1)⭐⭐⭐⭐⭐哈希表O(n)O(n)⭐⭐⭐⭐排序O(n log n)O(1)⭐⭐⭐分治O(n log n)O(log n)⭐⭐⭐总结要点说明核心思想投票算法多数元素正票多于负票关键操作count 0时换候选人相同加一不同减一时间复杂度O(n)空间复杂度O(1)