Concise O(n) time O(1) space by QuickSelect


  • 0
    L

    Find the first index i such that in the sorted array, a[i] >= n - i.
    This can be done by QuickSelect.

    class Solution {
    public:
        int hIndex(vector<int>& citations) {
            if(citations.empty()) return 0;
            int n = citations.size();
            int left = 0, right = n - 1, l, r;
            while(left < right) {
                // The following block is quickselect.
                l = left, r = right;
                while(l < r) {
                    while(l < r && citations[l] <= citations[r]) --r;
                    swap(citations[l], citations[r]);
                    while(l < r && citations[l] <= citations[r]) ++l;
                    swap(citations[l], citations[r]);
                }
                
                if(citations[l] >= n - l) right = l;
                else left = l + 1;
            }
            if(citations[left] < n - left) return 0;
            return n - left;
        }
    };
    

Log in to reply
 

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