Java 2 solutions, with sorting & without sorting


  • 1
    M

    With sorting O(N lgN):

        public int hIndex(int[] citations) {
            if(citations==null || citations.length==0) return 0;
            Arrays.sort(citations);
            final int N = citations.length;
            int res = 0;
            for(int i=0; i<N; i++){
                if(N-i <= citations[i])
                    return N-i;
            }
            return 0;
        }
    

    Without sorting O(N):

        public int hIndex(int[] citations){
            if(citations==null || citations.length==0) return 0;
            final int N = citations.length;
            int[] arr = new int[N+1];
            for(int i=0; i<N; i++){
                if(citations[i]>=N){
                    arr[N]++;
                } else {
                    arr[citations[i]]++;
                }
            }
            int counter=0, res = 0;
            for(int j=N; j>=0; j--){
                counter+= arr[j];
                if(counter>=j) return j;
            }
            return res;
        }
    

Log in to reply
 

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