Java O(n log n) time, O(1) space with Explanation


  • 4
    Y

    Idea is we need to find if there exist a position in sorted array, that citation[i] >= citation.length - i.

    for example:

    2 5 6 9 10 12 15
    7 6 5 4 3  2  1   <=== reverse index, tells how many elements(inclusive) to the right.
    

    in order to find the h-index. we need to find if there exist a position that citation[i] >= reverse index.

    So, like
    check elements 2 and after >= 7? --> No
    check elements 5 and after >= 6? --> No
    check elements 6 and after >= 5? --> Yes! This is the max "h" value, we return this 5.
    

    Code:

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

    Time Complexity O(n log n) + O(n) = O(n log n)
    Space Complexity O(1)


  • -1
    S

    Hi,

    I came across a situation: given citations = [3, 1, 7, 8, 9]. What will be the answer be?

    According to the definition of h-index on Wikipedia: "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."

    When h=3, the definition will be "A scientist has index 3 if 3 of his/her 5 papers have at least 3 citations each, and the other 2 papers have no more than 3 citations each." Obviously wrong....

    When h=4, the definition will be "A scientist has index 4 if 4 of his/her 5 papers have at least 4 citations each, and the other 1 papers have no more than 4 citations each." Obviously wrong....

    When h=2, the definition will be "A scientist has index 2 if 2 of his/her 5 papers have at least 2 citations each, and the other 3 papers have no more than 3 citations each." Obviously wrong....


  • 0
    Y

    Thanks for the followed comment. in your "h = 3" statement, I think that's right. there are 3 papers which is [7 8 9] have at least 3 citations and the other 2 paper which is [1 3] DO NOT have MORE THAN 3 citations each. May I know what is your reason claiming that this statement is obviously wrong?


Log in to reply
 

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