[Leetcode] H-Index H指數

xumenger 發布于2019-08-14 12:35 / 1041人閱讀

摘要：排序法復雜度時間空間思路先將數組排序，我們就可以知道對于某個引用數，有多少文獻的引用數大于這個數。代碼排序得到當前的指數數組映射法復雜度時間空間思路也可以不對數組排序，我們額外使用一個大小為的數組。

H-Index I

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.

排序法 復雜度

時間 O(NlogN) 空間 O(1)

思路

先將數組排序，我們就可以知道對于某個引用數，有多少文獻的引用數大于這個數。對于引用數citations[i]，大于該引用數文獻的數量是citations.length - i，而當前的H-Index則是Math.min(citations[i], citations.length - i)，我們將這個當前的H指數和全局最大的H指數來比較，得到最大H指數。

代碼

public class Solution {
    public int hIndex(int[] citations) {
        // 排序
        Arrays.sort(citations);
        int h = 0;
        for(int i = 0; i < citations.length; i++){
            // 得到當前的H指數
            int currH = Math.min(citations[i], citations.length - i);
            if(currH > h){
                h = currH;
            }
        }
        return h;
    }
}

數組映射法 復雜度

時間 O(N) 空間 O(N)

思路

也可以不對數組排序，我們額外使用一個大小為N+1的數組stats。stats[i]表示有多少文章被引用了i次，這里如果一篇文章引用大于N次，我們就將其當為N次，因為H指數不會超過文章的總數。為了構建這個數組，我們需要先將整個文獻引用數組遍歷一遍，對相應的格子加一。統計完后，我們從N向1開始遍歷這個統計數組。如果遍歷到某一個引用次數時，大于或等于該引用次數的文章數量，大于引用次數本身時，我們可以認為這是H指數。之所以不用再向下找，因為我們要取最大的H指數。那如何求大于或等于某個引用次數的文章數量呢？我們可以用一個變量，從高引用次的文章數累加下來。因為我們知道，如果有x篇文章的引用大于等于3次，那引用大于等于2次的文章數量一定是x加上引用次數等于2次的文章數量。

代碼

public class Solution {
    public int hIndex(int[] citations) {
        int[] stats = new int[citations.length + 1];
        int n = citations.length;
        // 統計各個引用次數對應多少篇文章
        for(int i = 0; i < n; i++){
            stats[citations[i] <= n ? citations[i] : n] += 1;
        }
        int sum = 0;
        // 找出最大的H指數
        for(int i = n; i > 0; i--){
            // 引用大于等于i次的文章數量，等于引用大于等于i+1次的文章數量，加上引用等于i次的文章數量 
            sum += stats[i];
            // 如果引用大于等于i次的文章數量，大于引用次數i，說明是H指數
            if(sum >= i){
                return i;
            }
        }
        return 0;
    }
}

H-Index II

Follow up for H-Index: What if the citations array is sorted in ascending order? Could you optimize your algorithm?

二分搜索法 復雜度

時間 O(logN) 空間 O(1)

思路

在升序的引用數數組中，假設數組長為N，下標為i，則N - i就是引用次數大于等于下標為i的文獻所對應的引用次數的文章數。如果該位置的引用數小于文章數，則說明則是有效的H指數，如果一個數是H指數，那最大的H指數一定在它的后面（因為是升序的）。根據這點就可已進行二分搜索了。這里min = mid + 1的條件是citations[mid] < n - mid，確保退出循環時min肯定是指向一個有效的H指數。

代碼

public class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        if(n == 0) return 0;
        int min = 0, max = citations.length - 1;
        while(min <= max){
            int mid = (min + max) / 2;
            // 如果該點是有效的H指數，則最大H指數一定在右邊
            if(citations[mid] < n - mid){
                min = mid + 1;
            // 否則最大H指數在左邊
            } else {
                max = mid - 1;
            }
        }
        // n - min是min點的H指數
        return n - min;
    }
}

云服務器 GPU云服務器 LeetCode LeetCode_String leetcode_35_SearchIn 指數平滑

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64578.html

H-Index & II

H-Index 題目鏈接：https://leetcode.com/problems... sort： public class Solution { public int hIndex(int[] citations) { if(citations == null || citations.length == 0) return 0; // sort ...

mochixuan 2019-08-14 17:25 評論0 收藏0
274. H-Index

摘要：題目解答滿足這個的最大值不會超過數組的因為如果超過了，就不可能有這么多的數。所以就是把所有可能的個至少有個的記下來，然后找出最大的。因為是從后向前掃的，所以當前的就是滿足條件的最大數。題目：Given an array of citations (each citation is a non-negative integer) of a researcher, write a fun...

xiaochao 2019-08-14 14:09 評論0 收藏0
leetcode50 Pow(x, n)自定義實現指數運算

摘要：題目要求此處為題目鏈接即用自己的代碼實現指數運算。指數為負數即求其倒數。思路一二分法計算這題的思路我之前的一篇博客思路基本相同。所以在能轉換為循環的情況下還是最好使用循環來解決。題目要求此處為題目鏈接即用自己的代碼實現指數運算。指數運算一般有兩種情況，即指數為整數和指數為負數的情況。指數為負數即求其倒數。思路一：二分法計算這題的思路我之前的一篇博客思路基本相同。有興趣的可以直接...

DoINsiSt 2019-08-16 10:32 評論0 收藏0
70道前端LeetCode題目集合及視頻講解（持續更新中...）

前端LeetCode刷題下面是已刷的題目的目錄。GitHub：https://github.com/cunzaizhuy...每日打卡更新中，歡迎關注。數組類 26 刪除排序數組中的重復項 27 移除元素 35 搜索插入位置 66 加1 80 medium 刪除排序數組中的重復項2 88 合并兩個有序數組 167 兩數之和II - 輸入有序數組 118 楊輝三角 169 easy 求眾數 1...

mayaohua 2019-08-26 10:46 評論0 收藏0