题目描述
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.
给一个长度为n
的数组,找出其中所有出现频率超过n/3
的元素。
举个例子:
Example 1:
Input: [3,2,3]
Output: [3]
Example 2:
Input: [1,1,1,3,3,2,2,2]
Output: [1,2]
Update at 2020_0625
重新梳理一下重点:
首先,两个候选人可以随机选择不一样的值,并将两个cnt
均初始化为0
。
一旦进入循环,则会出现两种情况:
第一种,直接蒙中一个候选人,则cnt++
。
否则,将当前元素替换成候选人。
第二点,循环中的所有条件都是互斥的,只能触发一次。
最后,记得判断候选人的出现频率是否大于n / 3
。
class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> ans = new LinkedList<>();
int len = nums.length;
if (len == 0) return ans;
int cand1 = 0;
int cand2 = 1;
int cnt1 = 0;
int cnt2 = 0;
for (int i = 0; i < len; i++){
int cur = nums[i];
if (cur == cand1){
cnt1++;
} else if (cur == cand2){
cnt2++;
} else if (cnt1 == 0){
cand1 = cur;
cnt1 = 1;
} else if (cnt2 == 0){
cand2 = cur;
cnt2 = 1;
} else {
cnt1--;
cnt2--;
}
}
int fre1 = 0;
int fre2 = 0;
for (int n: nums){
if (n == cand1) fre1++;
if (n == cand2) fre2++;
}
if (fre1 > len / 3) ans.add(cand1);
if (fre2 > len / 3 && !ans.contains(cand2)) ans.add(cand2);
return ans;
}
}
解法1
使用哈希表实现功能:
实现如下:
class Solution {
public List<Integer> majorityElement(int[] nums) {
int len = nums.length;
ArrayList<Integer> ans = new ArrayList<>();
HashMap<Integer, Integer> map = new HashMap<>();
for (int n: nums){
int cur = map.getOrDefault(n, 0) + 1;
if (cur > len / 3){
ans.add(n);
}
map.put(n, cur);
}
return ans.stream().distinct().collect(Collectors.toList());
}
}
解法2
Thanks @orbuluh
使用Boyer-Moore Majority Vote algorithm
算法,思想如下:
首先,假设两个候选人,比如0
和1
,并分别设置出现次数c1
和c2
。
然后,遍历数组,如果当前元素与候选人A
相等,则c1++
,若与候选人B
相等,则c2++
。
当上面两种情况均不符合,而此时c1 == 0
,则将当前元素设置为候选人A
,并且c1 = 1
,c2
同理。
若以上四种情况均不满足,则c1
和c2
分别减一。
以上只是获取两个候选人的步骤。
然后,分别计算候选人在原始数组中出现的频率,若大于n/3
,则转正
。
示意图如下:
实现如下:
class Solution {
public List<Integer> majorityElement(int[] nums) {
ArrayList<Integer> ans = new ArrayList<>();
if (nums == null || nums.length == 0) return ans;
int len = nums.length;
// Step1: Get two candidate.
int candidate1 = 0, candidate2 = 1;
int count1 = 0, count2 = 0;
for (int n: nums){
if (n == candidate1){
count1++;
} else if (n == candidate2){
count2++;
} else if (count1 == 0){
candidate1 = n;
count1 = 1;
} else if (count2 == 0){
candidate2 = n;
count2 = 1;
} else {
count1--;
count2--;
}
}
// Step2: Get the answer use the candidates.
int[] candidates = {candidate1, candidate2};
for (int i = 0; i < candidates.length; i++){
int cur = candidates[i];
int fre = 0;
for (int n: nums){
if (n == cur){
fre++;
}
}
if (fre > len / 3){
ans.add(cur);
}
}
return ans;
}
}
Enjoy it!
一位喜欢提问、尝试的程序员
(转载本站文章请注明作者和出处 姚屹晨-yaoyichen)