# My O(n) time solution use Java

• ``````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;
}
}``````

• diaozhatian hahahahahhahaha

• OMG!!!! Awesome!!!!

• diaofeile hahahahahha

• awesome code and comment hahahahahahaha

• Vote for your excellent code, and for China!

• diaozhatian, hahaha

• Diaozhatian! but this is not guaranteed as O(n)

• can you explain?

• LMAO when i read the comment, hahaha

• niubi diaozatian

• wow! New Bee!

• Nice comment, making this solution more understandable.

• Vote for China first, then for his code.

• 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];
for (int current = start; current < end; current++)
{
if (a[current] < p)
{
a[current] = temp;
}
}
}``````

• and I'm also from China, cheers!

• up for china.

• Niubility & diao zha tian! Vote U +1 before read the code.

• guoran diaozhatian

• leetcode已经被中国人玩坏了。。

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.