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


  • 0
    T
    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];
        }
     
    }
    

Log in to reply
 

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