描述
给定一个整型数组，找到主元素，它在数组中的出现次数严格大于数组元素个数的1/k。

数组中只有唯一的主元素

在线评测地址：领扣题库官网

样例1
输入: [3,1,2,3,2,3,3,4,4,4] and k=3, 
输出: 3.

样例2
输入: [1,1,2] and k=3, 
输出: 1.

挑战
要求时间复杂度为O(n)，空间复杂度为O(k)

算法：hashmap
当一个数的出现次数大于等于元素总数除以k向上取整时说明找到答案
将所有数字都用map存下来，并存下出现次数
遍历这个map，找到次数大于总数k分之一的元素
复杂度分析

时间复杂度O(n)

n为数组大小

空间复杂度O(n)

n为数组大小

代码

 public class Solution {
 * @param nums: a list of integers
 * @return: The majority number that occurs more than 1/3
 public int majorityNumber(List Integer nums, int k) {
 HashMap Integer,Integer map = new HashMap ();
 int n = nums.size();
 if(n == 0){
 return -1;
 int count = n/k + 1;
 //遍历nums
 Iterator it = nums.iterator();
 while(it.hasNext()){
 Integer tmp = (Integer)it.next();
 if(map.containsKey(tmp)){
 int m = (int)map.get(tmp) + 1;
 map.put(tmp, m);
 // 判断是否大于等于k分之一
 if(m = count){
 return tmp;
 else{
 map.put(tmp, 1);
 return nums.get(0);
}

更多题解参考：九章官网solution

本文转自网络，原文链接：https://developer.aliyun.com/article/783316