title
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.
Note: The algorithm should run in linear time and in O(1) space.
Example 1:
Input: [3,2,3]
Output: [3]
Example 2:
Input: [1,1,1,3,3,2,2,2]
Output: [1,2]
solution
给定一个整型数组，找到主元素，它在数组中的出现次数严格大于数组元素个数的三分之一。
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
vector<int> res;
if (nums.size() == 0) {
return res;
}
unordered_map<int, int> map1;
for (auto it : nums) {
map1[it]++;
}
for (auto it : map1) {
if (it.second > nums.size()/3) {
res.push_back(it.first);
}
}
return res;
}
};
投票
/**
* 本参考程序由九章算法用户提供。版权所有，转发请注明出处。
* - 九章算法致力于帮助更多中国人找到好的工作，授课老师均来自硅谷和国内的一线大公司在职工程师。
* - 现有的求职课程包括：九章算法班 2020升级版，算法强化班，算法基础班，北美算法面试高频题班，Java 高级工程师 P6+ 小班课，面试软技能指导 - BQ / Resume / Project 2020版
* - Design类课程包括：系统设计 System Design，面向对象设计 OOD
* - 专题及项目类课程包括：动态规划专题班，Big Data - Spark 项目实战，Django 开发项目课
* - 更多详情请见官方网站：http://www.jiuzhang.com/?utm_source=code
*/
public class Solution {
/**
* @param nums: A list of integers
* @return: The majority number that occurs more than 1/3
*/
public int majorityNumber(ArrayList<Integer> nums) {
// write your code
if (nums == null || nums.size() == 0) {
return -1;
}
int num1 = 0;
int num2 = 0;
int count1 = 0;
int count2 = 0;
for (int i = 0; i < nums.size(); i++) {
int newNum = nums.get(i);
if (count1 == 0) {
num1 = newNum;
count1++;
} else if (num1 == newNum) {
count1++;
} else if (count2 == 0) {
num2 = newNum;
count2++;
} else if (num2 == newNum) {
count2++;
} else {
count1--;
count2--;
}
}
count1 = 0;
count2 = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums.get(i) == num1) {
count1++;
}
if (nums.get(i) == num2) {
count2++;
}
}
return count1 > count2 ? num1 : num2;
}
}