275. H-Index II 递增排序后的论文引用量

［抄题］：

Given an array of citations in ascending order (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 hcitations each."

Example:

Input: citations = [0,1,3,5,6]
Output: 3 
Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had 
             received 0, 1, 3, 5, 6 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.

[暴力解法]：

时间分析：

空间分析：

[优化后]：

时间分析：

空间分析：

［奇葩输出条件］：

［奇葩corner case］：

［思维问题］：

从后往前积累的count = length - 从前往后的index

［一句话思路］：

甚至都不知道排序之后要用二分法，算是积累经验了

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

275. H-Index II 递增排序后的论文引用量

［一刷］：

明确这道题需要找的target： len - index代表文章数量
还是只有if elseif else的结构才是完整的

［二刷］：

［三刷］：

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

［总结］：

排序之后要用二分法

［复杂度］：Time complexity: O(lgn) Space complexity: O(n)

［英文数据结构或算法，为什么不用别的数据结构或算法］：

［算法思想：递归/分治/贪心］：

［关键模板化代码］：

非九章还加了等号，感觉就是因题目而异吧

while (lo <= hi) {
        int med = (hi + lo) / 2;

［其他解法］：

［Follow Up］：

［LC给出的题目变变变］：

[代码风格] ：

class Solution {
    public int hIndex(int[] citations) {
        //cc
        if (citations == null || citations.length == 0) return 0; 
        
        //ini: length
        int n = citations.length, start = 0, end = n - 1;
        
        //for loop
        while (start <= end) {
            int mid = (end + start) / 2;
            if (citations[mid] == n - mid) return n - mid;
            else if (citations[mid] > n - mid) end = mid - 1;
            else start = mid + 1;
        }
        
        return n - start;
    }
}

View Code

275. H-Index II 递增排序后的论文引用量

相关推荐