h index ii

发表于

算法：

url：https://leetcode.com/problems/h-index-ii/

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Given an array of citations sorted 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 h citations 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, her h-index is 3.
Note:

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

Follow up:

This is a follow up problem to H-Index, where citations is now guaranteed to be sorted in ascending order.
Could you solve it in logarithmic time complexity?

思路分析

[0,1,3,5,6]

数组长度 n，存在一个元素 h， 使得 n 中有 h个元素 大于等于h， 其他 （n-h）个元素 < h；

求h？

数组是有序的 递增数组

遍历 arr，存在 arr[i], 使得 n-i == arr[i]

Java解法

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int hIndex(int[] citations) {
        for(int i=citations.length-1; i>=0; --i) {
            if(citations[i] == citations.length-i) {
                return citations[i];
            }
        }
        return 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int hIndex(int[] citations) {
        int l = 1, r = citations.length;
        int ans = 0;
        while(l <= r){
            int m = l + ((r - l)>>1);
            int p = citations[citations.length - m];
            if(m == p){
                return m;
            }
            if(m > p){
                r = m - 1;
            }
            else{
                ans = Math.max(ans, m);
                l = m + 1;
            }
        }
        return ans;
    }
}

Python解法