本文主要是介绍LeetCode 229 Majority Element II (投票算法)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.
Example 1:
Input: nums = [3,2,3] Output: [3]
Example 2:
Input: nums = [1] Output: [1]
Example 3:
Input: nums = [1,2] Output: [1,2]
Constraints:
1 <= nums.length <= 5 * 10^4-10^9 <= nums[i] <= 10^9
Follow up: Could you solve the problem in linear time and in O(1) space?
题目链接：https://leetcode.com/problems/majority-element-ii/
题目大意：求频数超过n/3的数，要求O(1)空间，O(n)时间
题目分析：求频数最高的两个数字，然后判断这两个数字的频数是否超过n/3，求频数最高的两个数可以通过投票算法，大致思路：
设两个数为n1，n2，选票的相对值分别为c1，c2，注意这里记录的是相对值，不是绝对的频数，相对值可以理解为如果某次当前数字未被选中，则票数减1，选中则加1。若c1或c2为0则说明当前不存在票数明显多（频数高）的数字，则可以直接取当前数字继续往后累计票数
1ms，时间击败99.88%
class Solution {public List<Integer> majorityElement(int[] nums) {List<Integer> ans = new ArrayList<>();int c1 = 1, n1 = nums[0], c2 = 0, n2 = 0;for (int i = 1; i < nums.length; i++) {if (nums[i] == n1) {c1++;continue;}if (nums[i] == n2) {c2++;continue;}if (c1 == 0) {n1 = nums[i];c1 = 1;continue;}if (c2 == 0) {n2 = nums[i];c2 = 1;continue;}c1--;c2--;}c1 = 0;c2 = 0;for (int num : nums) {if (n1 == num) {c1++;} else if (n2 == num) {c2++;}}int minFreq = nums.length / 3; if (c1 > minFreq) {ans.add(n1);}if (c2 > minFreq) {ans.add(n2);}return ans;}
}这篇关于LeetCode 229 Majority Element II (投票算法)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
