# O(N) time ,O(1), using partition thought in quicksort 1ms

• ``````public class Solution {
/* partition to find the relationship of index and the tag - 1
if N - index < arr[index] - 1 return find [left, index - 1]
if N - index > arr[index] - 1 return find [index + 1, right]
else return N - index*/

public int hIndex(int[] citations) {
return quickfind(citations,0,citations.length - 1,citations.length);
}

private int quickfind(int[] arr, int left, int right, int N){
if (left == right) {
if (arr[left] < N - right) {
return arr[left];
}else {
return N - right;
}
}else if (left > right) {
return right + 1;
}
int l = left;
int r = right;
//three position function in quicksort
meadiaan(arr, l, (left + right) /2, r);
while (l < r) {
while (r > l) {
if (arr[r] < arr[left]) {
break;
}
r --;
}

while (l < r) {
if (arr[l] > arr[left]) {
break;
}
l ++;
}

if (l < r) {
swap(arr, l, r);
}
}
if (l == r) {
swap(arr, left, l);
}
if (N - l > arr[l]) {
return quickfind (arr, l + 1, right ,N);
}else if (N - l < arr[l]) {
return quickfind (arr, left, l , N);
}else {
return N - l;
}
}
private  void meadiaan(int[] a, int low, int i, int high) {
if (a[low]>a[high]){
if (a[i]<a[low]&&a[i]>a[high]){
swap(a,low,high);swap(a,i,low);
}else if (a[i]>a[low]){
swap(a,i,high);
}else swap(a,low,high);
}else {
if (a[i]>a[low]&&a[i]<a[high])swap(a,low,i);
else if (a[i]>a[high]){
swap(a,i,high);swap(a,low,i);
}
}
}
private void swap(int[] arr, int i, int j) {
if (arr[i] == arr[j]) {
return;
}

arr[i] ^= arr[j];
arr[j] ^= arr[i];
arr[i] ^= arr[j];
}

}
``````

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