https://leetcode.com/problems/h-index/
https://leetcode.com/mockinterview/session/result/xjcpjlh/
看了hint，不然的话，可能用的是排序的方法，O(NlgN)，现在的方法用了extra space，但是时间复杂度是O(N).
package com.company;
import java.util.*;
// https://discuss.leetcode.com/topic/32272/share-my-greedy-solution/2
class Solution {
public int hIndex(int[] citations) {
int[] rec = new int[citations.length];
for (int i=0; i<citations.length; i++) {
if (citations[i] >= 1 && citations[i] <= citations.length) {
rec[citations[i]-1]++;
}
else if (citations[i] > citations.length) {
rec[citations.length-1]++;
}
}
int count = 0;
for (int i=citations.length; i>0; i--) {
count += rec[i-1];
if (count >= i) {
return i;
}
}
return 0;
}
}
public class Main {
public static void main(String[] args) throws InterruptedException {
System.out.println("Hello!");
Solution solution = new Solution();
// Your Codec object will be instantiated and called as such:
int[] citations = {3, 0, 6, 1, 5};
int ret = solution.hIndex(citations);
System.out.printf("ret:%d\n", ret);
System.out.println();
}
}