LeetcodeÖг£ÓÃÅÅÐò Ö® O(n)ʱ¼ä¸´ÔÓ¶ÈÅÅÐò

ͨ¹ýʹÓöîÍâµÄ¿Õ¼ä£¬´ïµ½O(n)µÄʱ¼ä¸´ÔӶȵÄÅÅÐò·½·¨

Ö±½ÓÉÏ´úÂ룺

import java.util.HashMap;

public class Ranking_O_n {
    public int[]ranking(int []nums){
        int []ranked=new int[nums.length];
        int times=0, min=0,max=0,index=0;
        HashMap<Integer,Integer>h=new   HashMap<Integer,Integer>();

        for(int n:nums){
            if(n<min)min=n;
            if(n>max)max=n;
            if(h.containsKey(n)){
                times=h.get(n);
                times++;
                h.put(n,times);
            }
            else 
                h.put(n, 1);
        }
        for(int n=min;n<=max;n++){
            if(h.containsKey(n)){
                times=h.get(n);
                for(int i=0;i<times;i++){
                    ranked[index]=n;
                    index++;
                }
            }
        }


        return ranked;
    }
    public static void main(String[]args){
        Ranking_O_n c=new Ranking_O_n();
        int[]nums={1,2,1,1,2,3,5,6,10,2,55,2,33,44,28,48,21};
        for(int n:c.ranking(nums)){
            System.out.print(n+" ");
        }
    }
}