Majority Number III
今天是一道数学计算的题目，来自LintCode，在LintCode的Ladder中被归为Greedy算法一类。难度为Medium，Acceptance为26%。是之前Majority Element （回复016查看）和Majority Element II（回复017查看）的深入。但是该题在Leetcode上没有，是LintCode上的题目。
题目如下
Given an array of integers and a number k, the majority number is the number that occurs
more than 1/kof the size of the array.
Find it.
Example
Given [3,1,2,3,2,3,3,4,4,4] and k=3, return 3.
Note
There is only one majority number in the array.
Challenge
O(n) time and O(k) extra space
解题思路及代码见阅读原文
回复0000查看更多题目
解题思路
首先，该题还是求出现次数多的数字。那么，借鉴的思路，我们需要用变量记录k-1个出现次数最多的数字和这些数字出现的次数。
然后，这里不同的是这里不止有2个数字，而是k-1个。那么，如果这里还是按照一样，分别用k-1个变量记录这些数字；再用k-1个变量记录这些数字出现的次数，显然是效率极低的。因为在遍历数组时，需要和每一个数字作比较。那么应该采用什么数据结构呢？很显然，可以采用hashmap来保存这些数字和次数，以数字为键，以次数为值。
最后，就是找到这k-1个数的逻辑，参考，逻辑几乎是一样的，即找到相同的数则次数加1；当次数为0时，从hashmap中移除；若找不到相同的数字，且hashmap的内的元素个数小于k-1，则加入hashmap。
有了思路，下面来看代码。
代码如下
java版
public class Solution {
/**
* @param nums: A list of integers
* @param k: As described
* @return: The majority number
*/
public int majorityNumber(ArrayList<Integer> nums, int k) {
// write your code
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i : nums) {
Integer count = map.get(i);
if(count != null) {
map.put(i, count + 1);
} else if(map.size() < k - 1){
map.put(i, 1);
} else {
List<Integer> list = new LinkedList<Integer>();
for(Integer j : map.keySet()) {
Integer old = map.get(j) - 1;
map.put(j, old);
if(old <= 0) {
list.add(j);
}
}
for(int j : list) {
map.remove(j);
}
}
}
for(Integer j : map.keySet()) {
map.put(j, 0);
}
for(int i : nums) {
Integer count = map.get(i);
if(count != null) {
if(++count > (nums.size() / k)) return i;
map.put(i, count);
}
}
return 0;
}
}
关注我
该公众号会每天推送常见面试题，包括解题思路是代码，希望对找工作的同学有所帮助
