import java.util.Arrays; /** * https://leetcode.com/articles/h-index/ */ /** * TestCase * [0] * [1] * [] * [100] */ public class HIndex { // 耗时4ms，时间复杂度O(nlgn) public int hIndex(int[] citations) { Arrays.sort(citations); int hIndex = 0; for (int i = citations.length - 1; i >= 0; i--) { hIndex = Math.max(hIndex, Math.min(citations.length - i, citations[i])); } return hIndex; } // 耗时1ms，时间复杂度O(n) public int hIndex2(int[] citations) { /** * 大于文章数的引用可以合并到一起 */ int n = citations.length; int[] f = new int[n + 1]; for (int k : citations) { f[Math.min(k, n)]++; } int hindex = 0; /** * i表示引用数，j表示大于等于该引用数的总文章数 */ for (int i = n, j = 0; i >= 0; i--) { j += f[i]; hindex = Math.max(hindex, Math.min(j, i)); } return hindex; } }