Majority Number III
今天是一道數(shù)學(xué)計算的題目，來自LintCode黑滴，在LintCode的Ladder中被歸為Greedy算法一類赂乐。難度為Medium，Acceptance為26%涕烧。是之前Majority Element （回復(fù)016查看）和Majority Element II（回復(fù)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
解題思路及代碼見閱讀原文
回復(fù)0000查看更多題目
解題思路
首先景鼠，該題還是求出現(xiàn)次數(shù)多的數(shù)字。那么，借鑒的思路铛漓，我們需要用變量記錄k-1個出現(xiàn)次數(shù)最多的數(shù)字和這些數(shù)字出現(xiàn)的次數(shù)溯香。
然后，這里不同的是這里不止有2個數(shù)字浓恶，而是k-1個玫坛。那么，如果這里還是按照一樣包晰，分別用k-1個變量記錄這些數(shù)字湿镀；再用k-1個變量記錄這些數(shù)字出現(xiàn)的次數(shù)，顯然是效率極低的伐憾。因為在遍歷數(shù)組時勉痴，需要和每一個數(shù)字作比較。那么應(yīng)該采用什么數(shù)據(jù)結(jié)構(gòu)呢树肃？很顯然蒸矛，可以采用hashmap來保存這些數(shù)字和次數(shù)，以數(shù)字為鍵胸嘴，以次數(shù)為值雏掠。
最后，就是找到這k-1個數(shù)的邏輯劣像，參考乡话，邏輯幾乎是一樣的，即找到相同的數(shù)則次數(shù)加1耳奕；當(dāng)次數(shù)為0時绑青，從hashmap中移除；若找不到相同的數(shù)字吮铭，且hashmap的內(nèi)的元素個數(shù)小于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;
}
}
關(guān)注我
該公眾號會每天推送常見面試題，包括解題思路是代碼纸肉，希望對找工作的同學(xué)有所幫助
