Better solution than Hint, no extra space


  • 14
    J

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

  • 0
    Z

    This is called Quickselect. This is called Quickselect


  • 0
    J

    Well, no really. QuickSelect is to find the Kth item. In this question, you don't know the exact index in ahead. But if QuickSelect can make it easier to understand for you, I'm fine with it.


  • 0
    T

    The worse case complexity would be O(n^2) instead of O(n). Average complexity would be O(n) as you stated


  • 0
    J

    Yep, sorry for the confusion, but just like quicksort or quick select, in most case, it's a better solution. thanks


  • 0
    C

    The one used to find the Kth item is called "Randomized Selection"


  • 0
    Z

    Still got confused why this will work..


Log in to reply
 

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