One pass method with O(n) time and space.


  • 0
    Z
    public class Solution {
        public int hIndex(int[] citations) {
            int h = 0;
    		if(citations == null || citations.length == 0){
    			return h;
    		}
    		int len = citations.length;
    		int[] map = new int[len+1];
    		for(int i = 0; i < citations.length; i++){
    			if(citations[i] > h){
    				if(map[h] == 0){
    					h++;
    				} 
    				else{
    					map[h]--;
    				}
    				if(citations[i]>len){
    					map[len]++;
    				}
    				else{
    					map[citations[i]]++;
    				}
    			}
    		}
    		return h;
        }
    }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.