274. H-Index

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

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

解答：
滿足這個index的最大值不會超過citations數(shù)組的len, 因為如果超過了，就不可能有這么多的paper數(shù)。所以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是犧牲空間來換取時間，那就用另外一個數(shù)組來存當前index存在的文章數(shù)，然后從后往前相加，如果滿足條件就輸出這個最大的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就是滿足條件的最大數(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也不會大于數(shù)組的長度，所以，超過數(shù)組長度的citation可以都記在len里
            if (citations[i] > len) {
                arr[len] += 1;
            } else {
                //arr的index就是一篇文章中citation的個數(shù)，arr的值就是有這么多citation的文章的個數(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;
    }

GPU云服務器云服務器

文章版權歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/64838.html

[Leetcode] H-Index H指數(shù)

摘要：排序法復雜度時間空間思路先將數(shù)組排序，我們就可以知道對于某個引用數(shù)，有多少文獻的引用數(shù)大于這個數(shù)。代碼排序得到當前的指數(shù)數(shù)組映射法復雜度時間空間思路也可以不對數(shù)組排序，我們額外使用一個大小為的數(shù)組。 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
軌跡數(shù)據(jù)壓縮算法

摘要：數(shù)據(jù)問題解壓縮結(jié)果計算高主要運行結(jié)果列表容差計算通過的內(nèi)容算法點列表第一個點最后一個點容差軌跡結(jié)果原始圖壓縮圖數(shù)據(jù) 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參數(shù)化三種方式

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

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

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

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