做完这题我就慌了,怎么会有这样的题目
資深大佬 : zzzrf 6
原题目的地址在这里,大佬们可以看看有没有更优的解法
做出来觉得和 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); } }
大佬有話說 (3)