Share my C++ solution using O(1) space and O(n) average time


  • 2
    R

    the algorithm is binary search and the partition of qsort. Here is my code:

    class Solution {
    public:
        int hIndex(vector<int>& citations) {
            int l = 0, r = citations.size(), ans = 0; 
            while (l < r) {
                int pix = citations[l];
                int i = l, j = r; 
                while (i < j) {  
                    while (i < --j && citations[j] < pix); 
                    while (++i < j && citations[i] >= pix);
                    if (i < j) {
                        swap(citations[i], citations[j]); 
                    }
                }
                swap(citations[j], citations[l]); 
                if (pix >= j + 1) {
                    ans = j + 1; 
                    l = j + 1; 
                } else {
                    r = j; 
                }
            }
            return l; 
        }
    };

Log in to reply
 

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