Using sorting - really small solution


  • 2
    N

    We can optimize this from O(n) to O(logn) (leaving aside the time complexity of sorting) by travelling the array as a binary tree using mid, low and high

    public int hIndex(int[] a) {
                if(a==null)
                    return 0;
                Arrays.sort(a);
                int len = a.length;
                int i = len-1, h = 1, hMax = 0;
                while(i >= 0){
                    if(h <= a[i] && h == len-i){
                        hMax = Math.max(h, hMax);
                    }
                    h++; i--;
                }
                return hMax;
            }

Log in to reply
 

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