Have a better solution without extra space.

Using in place divide (not sort) and the time in normal case is n + n/2 + n/4 + ... ~= 2n = O(n).

In worst case is: O(n^2), but just like quicksort, in most cases, it's a better solution.

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;
}
// divide the array by the last item and return the new index of this partition item.
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;
}
```