LC.P274[H指数]

方法一：二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int hIndex(int[] citations) {
        int left = 0, right = citations.length;
        while (left < right) {
            int mid = left + right + 1 >> 1;
            int s = 0;
            for (int x : citations) {
                if (x >= mid) ++s;
            }
            if (s >= mid) left = mid;
            else right = mid - 1;
        }
        return left;
    }
}
  • 时间复杂度：$O(nlogn)$
  • 空间复杂度：$O(1)$

方法二：排序

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        int n = citations.length;
        for (int h = n; h > 0; --h) {
            if (citations[n - h] >= h) {
                return h;
            }
        }
        return 0;
    }
}
  • 时间复杂度：$O(nlogn)$
  • 空间复杂度：$O(logn)$

方法三：计数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int[] cnt = new int[n + 1];
        for (int x : citations) {
            ++cnt[Math.min(x, n)];
        }
        for (int h = n, s = 0; ; --h) {
            s += cnt[h];
            if (s >= h) {
                return h;
            }
        }
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$