Java bucket sort O(n) solution with detail explanation


  • 140
    Y

    This type of problems always throw me off, but it just takes some getting used to. The idea behind it is some bucket sort mechanisms. First, you may ask why bucket sort. Well, the h-index is defined as the number of papers with reference greater than the number. So assume n is the total number of papers, if we have n+1 buckets, number from 0 to n, then for any paper with reference corresponding to the index of the bucket, we increment the count for that bucket. The only exception is that for any paper with larger number of reference than n, we put in the n-th bucket.

    Then we iterate from the back to the front of the buckets, whenever the total count exceeds the index of the bucket, meaning that we have the index number of papers that have reference greater than or equal to the index. Which will be our h-index result. The reason to scan from the end of the array is that we are looking for the greatest h-index. For example, given array [3,0,6,5,1], we have 6 buckets to contain how many papers have the corresponding index. Hope to image and explanation help.

    Buckets

    public int hIndex(int[] citations) {
        int n = citations.length;
        int[] buckets = new int[n+1];
        for(int c : citations) {
            if(c >= n) {
                buckets[n]++;
            } else {
                buckets[c]++;
            }
        }
        int count = 0;
        for(int i = n; i >= 0; i--) {
            count += buckets[i];
            if(count >= i) {
                return i;
            }
        }
        return 0;
    }
    

  • 3

    活学活用,举一反三,👍


  • 14
    X

    I give you 99 points, one less point means that you might get proud of 100 points.


  • 2
    L

    why we don't check the N - h mentioned in the problem?


  • 0
    R

    厉害厉害,受教了大神!!!


  • -5

    Your answer is wrong. Consider a simple example [4,4,4,3]: your program return 3. The explanation for h is "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each".

    In the example, that will be that a scientist has index 3 if 3 of his/her 4 papers have at least 3 citations each, and the other 1 papers have no more than 3 citations each.

    Clearly, the answer is wrong.


  • 1
    F

    @huimengpaopao It seems you are giving an explanation why yourself is wrong...


  • 0
    A

    Nice O(n) solution. I reproduced in python :-)

    class Solution(object):
        def hIndex(self, citations):
            n = len(citations)
            buckets = [0 for _ in range(n + 1)]
            
            for num in citations:
                if num >= n:
                    buckets[n] += 1
                else:
                    buckets[num] += 1
                    
            count = 0
            
            for i in reversed(range(len(buckets))):
                count += buckets[i]
                
                if count >= i:
                    return i
                    
            return 0
            
    

  • 0
    F

    Thanks a lot for the explanation and excellent solution!


  • 0
    O

    Such a fabulous solution! Newbee!


  • 2
    V

    Is this a bucket sort? It is a counting sort!!!!


Log in to reply
 

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