Majority Element II
今天是一到有关数学计算的题目,是Majority Element(回复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.
解题思路及代码见阅读原文
回复0000查看更多题目
思路如下
首先,在Majority Element一题中,我们要找出现次数多于一半的数,那么这样的数字只有1个。在本题中,要找大于三分之一的数字,那么这样的数最多有2个。
然后,我们知道了有2个数字之后,就可以用2个变量记录两个出现次数最多的数字。这个方法和Majority Element类似。
最后,遍历整个数组,看这2个数的出现次数是否都多于三分之一。
代码如下
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;
}
关注我
该公众号会每天推送常见面试题,包括解题思路是代码,希望对找工作的同学有所帮助