274. H-Index

xiaochao 發(fā)布于2019-08-14 14:09 / 1195人閱讀

摘要：題目解答滿足這個(gè)的最大值不會(huì)超過數(shù)組的因?yàn)槿绻^了，就不可能有這么多的數(shù)。所以就是把所有可能的個(gè)至少有個(gè)的記下來，然后找出最大的。因?yàn)槭菑暮笙蚯皰叩?，所以?dāng)前的就是滿足條件的最大數(shù)。

題目：
Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher"s h-index.

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."

For example, given citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, his h-index is 3.

Note: If there are several possible values for h, the maximum one is taken as the h-index.

Hint:

An easy approach is to sort the array first.
What are the possible values of h-index?
A faster approach is to use extra space.

解答：
滿足這個(gè)index的最大值不會(huì)超過citations數(shù)組的len, 因?yàn)槿绻^了，就不可能有這么多的paper數(shù)。所以brute force就是把所有可能的n個(gè)paper至少有n個(gè)citation的n記下來，然后找出最大的n。
代碼：

public int hIndex(int[] citations) {
        int maxHIndex = 0;
        for (int i = citations.length; i >= 0; i--) {
            int citNum = i;
            int count = 0;
            for (int j = 0; j < citations.length; j++) {
                if (citations[j] >= citNum) {
                    count++;
                }
            }
            if (count >= citNum) {
                maxHIndex = Math.max(maxHIndex, citNum);
            }
        }
        
        return maxHIndex;
    }

Follow up是犧牲空間來換取時(shí)間，那就用另外一個(gè)數(shù)組來存當(dāng)前index存在的文章數(shù)，然后從后往前相加，如果滿足條件就輸出這個(gè)最大的index。
舉個(gè)例子：

citations: 3, 0, 6, 1, 5
arr: 0 1 2 3 4 5
val: 1 1   1   2

那么從后向前掃的時(shí)候，記一個(gè)count,掃到arr(5)的時(shí)候，count=2 < 5, 不滿足；掃arr(4),count＝2 < 4, 不滿足；掃arr(3), count=2+1=3 == 3, 滿足。因?yàn)槭菑暮笙蚯皰叩?，所以?dāng)前的index就是滿足條件的最大數(shù)。
代碼：

public int hIndex(int[] citations) {
        if (citations == null || citations.length == 0) return 0;
        
        int len = citations.length;
        int[] arr = new int[len + 1];
        for (int i = len - 1; i >= 0; i--) {
            //最大的index也不會(huì)大于數(shù)組的長度，所以，超過數(shù)組長度的citation可以都記在len里
            if (citations[i] > len) {
                arr[len] += 1;
            } else {
                //arr的index就是一篇文章中citation的個(gè)數(shù)，arr的值就是有這么多citation的文章的個(gè)數(shù)
                arr[citations[i]] += 1;
            }
        }
        
        int count = 0;
        for (int i = len; i >= 0; i--) {
            count += arr[i];
            if (count >= i) {
                return i;
            }
        }
        return 0;
    }