274. H-Index

xiaochao 發布于2019-08-14 14:09 / 1157人閱讀

摘要：題目解答滿足這個的最大值不會超過數組的因為如果超過了，就不可能有這么多的數。所以就是把所有可能的個至少有個的記下來，然后找出最大的。因為是從后向前掃的，所以當前的就是滿足條件的最大數。

題目：
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.

解答：
滿足這個index的最大值不會超過citations數組的len, 因為如果超過了，就不可能有這么多的paper數。所以brute force就是把所有可能的n個paper至少有n個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是犧牲空間來換取時間，那就用另外一個數組來存當前index存在的文章數，然后從后往前相加，如果滿足條件就輸出這個最大的index。
舉個例子：

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

那么從后向前掃的時候，記一個count,掃到arr(5)的時候，count=2 < 5, 不滿足；掃arr(4),count＝2 < 4, 不滿足；掃arr(3), count=2+1=3 == 3, 滿足。因為是從后向前掃的，所以當前的index就是滿足條件的最大數。
代碼：

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也不會大于數組的長度，所以，超過數組長度的citation可以都記在len里
            if (citations[i] > len) {
                arr[len] += 1;
            } else {
                //arr的index就是一篇文章中citation的個數，arr的值就是有這么多citation的文章的個數
                arr[citations[i]] += 1;
            }
        }
        
        int count = 0;
        for (int i = len; i >= 0; i--) {
            count += arr[i];
            if (count >= i) {
                return i;
            }
        }
        return 0;
    }

云服務器 GPU云服務器

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

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

[Leetcode] H-Index H指數

摘要：排序法復雜度時間空間思路先將數組排序，我們就可以知道對于某個引用數，有多少文獻的引用數大于這個數。代碼排序得到當前的指數數組映射法復雜度時間空間思路也可以不對數組排序，我們額外使用一個大小為的數組。 H-Index I Given an array of citations (each citation is a non-negative integer) of a research...

xumenger 2019-08-14 12:35 評論0 收藏0
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
軌跡數據壓縮算法

摘要：數據問題解壓縮結果計算高主要運行結果列表容差計算通過的內容算法點列表第一個點最后一個點容差軌跡結果原始圖壓縮圖數據 P0,107.605,137.329 P1,122.274,169.126 P2,132.559,179.311 P3,153.324,184.276 P4,171.884,174.654 P5,186.408,168.634 P6,196.566,145.204 P7...

TANKING 2019-07-31 11:13 評論0 收藏0
httprunner2.5.7參數化三種方式

摘要：重點以上版本參數化都需要借助進行參數化，需嚴格縮進格式，不能用控制縮進，只能用空格控制直接引用列表進行參數化引用文件進行參數化借助輔助函數進行參數化定義項目的文件框架建立四個文件夾，分別用來存放接口用例用例集測試數據編寫接口腳本在文件下，重點：2.x以上版本參數化都需要借助testsuit...

Jokcy 2021-11-11 16:54 評論0 收藏0
從零開始使用node讀取txt處理后導出excel

摘要：安裝執行版本號，例如以下語句可以安裝幾的版本好像在墻內只能找到以前的版本使用可以查看現有的版本，可以支持模糊切換。一直說要好好學習，總結知識什么的。一直覺得沒有時間。周一終于提交了論文盲審。決定從今天每周都總結一次自己的所學。希望自己能堅持。任務描述：一個醫學系的同學要分析一個叫TCGA的數據庫，每個實驗文件是txt，格式如下： hsa-miR-1228* 5.185500...

frank_fun 2019-08-20 15:46 評論0 收藏0