Majority Element II
今天是一到有關(guān)數(shù)學(xué)計(jì)算的題目，是Majority Element（回復(fù)016查看）的深入羹唠，來自LeetCode芜茵，難度為Medium，Acceptance為23.6%眷唉。
題目如下
Given an integer array of size n, find all elements that appear more than
? n/3 ?times. The algorithm should run in linear time and in O(1) space.
解題思路及代碼見閱讀原文
回復(fù)0000查看更多題目
思路如下
首先，在Majority Element一題中损肛，我們要找出現(xiàn)次數(shù)多于一半的數(shù)厢破，那么這樣的數(shù)字只有1個(gè)。在本題中治拿，要找大于三分之一的數(shù)字摩泪，那么這樣的數(shù)最多有2個(gè)。
然后劫谅，我們知道了有2個(gè)數(shù)字之后见坑，就可以用2個(gè)變量記錄兩個(gè)出現(xiàn)次數(shù)最多的數(shù)字。這個(gè)方法和Majority Element類似捏检。
最后荞驴，遍歷整個(gè)數(shù)組，看這2個(gè)數(shù)的出現(xiàn)次數(shù)是否都多于三分之一贯城。
代碼如下
java版
public class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> list = new ArrayList<Integer>();
if(null == nums)
return list;
int num1 = 0, num2 = 0;
int count1 = 0, count2 = 0;
for(int i : nums) {
if(count1 == 0 || num1 == i) {
num1 = i;
count1++;
} else if(count2 == 0 || num2 == i) {
num2 = i;
count2++;
} else {
count1--;
count2--;
}
}
count1 = 0;
count2 = 0;
for(int i : nums) {
if(i == num1)
count1++;
else if(i == num2)
count2++;
}
if(count1 > nums.length / 3)
list.add(num1);
if(count2 > nums.length / 3)
list.add(num2);
return list;
}
}
c++版
vector<int> majorityElement(vector<int>& nums) {
int cnt1=0, cnt2=0;
int a,b;
for(int n: nums){
if (cnt1 == 0 || n == a){
cnt1++;
a = n;
}
else if (cnt2 == 0 || n==b){
cnt2++;
b = n;
}
else{
cnt1--;
cnt2--;
}
}
cnt1=cnt2=0;
for(int n: nums){
if (n==a) cnt1++;
else if (n==b) cnt2++;
}
vector<int> result;
if (cnt1 > nums.size()/3) result.push_back(a);
if (cnt2 > nums.size()/3) result.push_back(b);
return result;
}
關(guān)注我
該公眾號(hào)會(huì)每天推送常見面試題熊楼，包括解題思路是代碼，希望對(duì)找工作的同學(xué)有所幫助
image
