筆試面試算法經典-找到數組中出現次數大于N/k的數（Java）

【題目】

給定一個整型數組arr，再給定一個整數k，列印所有出現次數大于 N/K 的數。如果沒有這樣的數，列印提示資訊。

【要求】

時間複雜度為O（N*K）,額外空間複雜度為O（K）。

【思路】

每次從數組中删除 K 個不同的數，如果某個數的次數大于 N/K ，這個數最後肯定會剩下來，數學證明：假設 X 的次數為 (N/k+1) > N/K ,如果每次删除 k個不同的數最後數組裡面剩餘的數裡面沒有 X 那麼肯定删除的次數大于等于（N/k+1）>N/K , 那麼：K*（N/K+1）>N,不成立因為數組中隻有 N 個數不可能删除掉 比 N 還多的數。

注意：删除後剩餘的數不一定全是次數大于 N/K 的數，例如：{1，2，3} k=2, 删除後數組中還剩餘 3，但是 3 的次數為 1 ，是以還要看剩餘的數的次數是不是大于 N/K.

算法過程：大小為 K 的空間，來儲存不同的數，當有K個不同的數時，将每個數的次數減 1當 将次數為1的數删除，如果空間中有這個數時，則将這個數的次數加 1 。

下面是數組arr[]={1 ,2 ,3 ,3 ,5 ,2 ,2 ,3 ,3 ,3 ,5 ,6 ,2 ,2 ,2 ,3 , 3}處理的簡單過程圖：

代碼：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map.Entry;
public class GetKMajor {

    public static void main(String[] args) {
        int arr[]={,,,,,,,,,,,,,,,,};
        int k=;
        getKMajor(arr,k);
    }
    public static void getKMajor(int arr[],int k)
    {
        if(k<)
        {
            return;
        }
        HashMap<Integer, Integer> hashMap=new HashMap<Integer, Integer>();
        for(int i=;i<arr.length;i++)
        {
        //hashmap由于儲存k個不同的數，當hashmap中有k個不同的數時，則每個數的次數減1，
        //如果某個數的次數為0，則将其從hashmap中删除。
            if(hashMap.containsKey(arr[i]))
            {
            //如果hashmap中存在這個數，則将這個數的次數加1
                hashMap.put(arr[i],hashMap.get(arr[i])+);

            }
            else {
                if(hashMap.size()==k-)
                {
                    //如果hashmap中不存在這個數，如此時hashmap中存在k-1個不同的數則将
                    //hashmap中的每個數的次數減1
                    AllminusOne(hashMap);
                }
                else {
                //hashmap中的不同數個數小于k-1，時将該數加入到hashmap中。
                    hashMap.put(arr[i], );

                }
            }
        }   
        for(Entry<Integer, Integer> set:hashMap.entrySet())
        {
            Integer key=set.getKey();
            hashMap.put(key, );    
            //對hashmap中剩下的每個數先将次數指派為0，為後面計算每個數的次數是否大于N/K做準備。        
        }
        for(int i=;i<arr.length;i++)
        {
            if(hashMap.containsKey(arr[i]))
            {
                hashMap.put(arr[i], hashMap.get(arr[i])+);
            }
        }
        for(Entry<Integer, Integer> set:hashMap.entrySet())
        {
            Integer key=set.getKey();
            Integer value=set.getValue();
            if(value>arr.length/k)
                System.out.println(key);
                //如果某個數的次數大于K/N則将其輸出。
        }
    }
    public static void AllminusOne(HashMap<Integer, Integer> hashMap)
    {
    //将hashmap中的每個數的次數減1，将減 1 後次數為0 的從hashmap中删除。
        ArrayList<Integer> removelist=new ArrayList<Integer>();
        for(Entry<Integer, Integer> set:hashMap.entrySet())
        {
            Integer key=set.getKey();
            Integer value=set.getValue();
            if(value==)
            {
                removelist.add(key);
            }else {             
                hashMap.put(key, value-);      
            }
        }
        for(Integer removekey:removelist)
        {
            hashMap.remove(removekey);
        }

    }
}