首页 > 代码库 > LintCode-Majority Number III
LintCode-Majority Number III
Given an array of integers and a number k, the majority number is the number that occurs more than 1/k of the size of the array. Find it.
Note
There is only one majority number in the array.
Example
For [3,1,2,3,2,3,3,4,4,4] and k = 3, return 3
Challenge
O(n) time and O(k) extra space
Analysis:
Keep k-1 pointers and counters. Use HashMap to store numbers and counters, every delete operation will cost k-1, however, the max times of deletion is n/(k-1) because deletion only happens when there are (k-1) numbers in the map. So the overall complexity is still O(n).
Solution:
1 public class Solution { 2 /** 3 * @param nums: A list of integers 4 * @param k: As described 5 * @return: The majority number 6 */ 7 public int majorityNumber(ArrayList<Integer> nums, int k) { 8 if (nums==null || nums.size()==0) return 0; 9 10 int len = nums.size();11 Map<Integer,Integer> nMap = new HashMap<Integer,Integer>();12 nMap.put(nums.get(0),1);13 for (int i=1;i<len;i++)14 if (nMap.containsKey(nums.get(i))){15 int val = nMap.get(nums.get(i))+1;16 if (val==0) nMap.remove(nums.get(i)); 17 else nMap.put(nums.get(i),val);18 } else {19 //if the number of existing numbers is less than k-1, then just add one.20 if (nMap.size()<k-1){21 nMap.put(nums.get(i),1);22 } else {23 List<Integer> keyList = new ArrayList<Integer>();24 //decrease the value of every key by 1.25 for (Map.Entry en : nMap.entrySet()){26 int key = (int) en.getKey();27 int value = http://www.mamicode.com/(int) en.getValue();28 value--;29 if (value=http://www.mamicode.com/=0) keyList.add(key);30 nMap.put(key,value);31 }32 for (int key : keyList) nMap.remove(key);33 }34 }35 36 for (Map.Entry en: nMap.entrySet()) en.setValue(0);37 int num = 0, count = 0;38 for (int i=0;i<len;i++)39 if (nMap.containsKey(nums.get(i))){40 int val = nMap.get(nums.get(i))+1;41 if (val>count){42 num = nums.get(i);43 count = val;44 }45 nMap.put(nums.get(i),val);46 } 47 return num;48 49 }50 }
NOTE: It is a very good problem to practice HashMap and its iteration.
LintCode-Majority Number III
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。