public class Solution {
// 9.3 70 years diaoZhaTian China jiaYou
public int hIndex(int[] citations) {
int length = citations.length;
if (length == 0) {
return 0;
}
int[] array2 = new int[length + 1];
for (int i = 0; i < length; i++) {
if (citations[i] > length) {
array2[length] += 1;
} else {
array2[citations[i]] += 1;
}
}
int t = 0;
int result = 0;
for (int i = length; i >= 0; i) {
t = t + array2[i];
if (t >= i) {
return i;
}
}
return 0;
}
}
My O(n) time solution use Java


Have a better solution without extra space. Using in place divide (not sort) and the time in average case is n + n/2 + n/4 + ... ~= 2n = O(n). in worst case is O(n2).
But in most cases, it has a better running time.It beats 100% submits at least in my desktop.
Here is the code:
public int hIndex(int[] citations) { int length = citations.length; int start = 0; int end = length  1; int hIndex = 0; while (start <= end) { int current = divideByPartition(citations, start, end); if (length  current <= citations[current]) { hIndex = length  current; end = current  1; } else start = current + 1; } return hIndex; } private int divideByPartition(int[] a, int start, int end) { if (start == end) return end; int p = a[end]; int head = start; for (int current = start; current < end; current++) { if (a[current] < p) { int temp = a[head]; a[head] = a[current]; a[current] = temp; head++; } } a[end] = a[head]; a[head] = p; return head; }