C++ O(n) time, O(1) extra space


  • 0
    A

    1st loop makes citations[i] = count of occurrence of citation = (i+1) for i from 0 to n-2,
    citations[n-1] = count of occurrence of citation >= n.
    2nd loop then turns citations[i] to count of occurrence of citation >= i.

    "MSB" is as a temporal mark for those i we visited before iterating it and can make sure this algorithm an O(n) in time complexity.

    #define MSB (1 << 30)
    class Solution {
    public:
        int hIndex(vector<int>& citations) {
         int n = citations.size();
            if (n == 0) return 0;
            
            for (int k = n-1; k >= 0; ) {
                if ((citations[k] & MSB)) {
                    citations[k--] -= MSB;
                    continue;
                }
                
                int idx = min(citations[k]-1, n-1);
                if (idx == k) {
                    citations[k--] = 1;
                } else if (idx > k) {
                    citations[idx]++;
                    citations[k--] = 0;
                } else {
                    if (citations[k] > 0) {
                        if ((citations[idx] & MSB)) {
                            citations[idx]++;
                            citations[k--] = 0;
                        } else {
                            if (citations[k] == citations[idx]) {
                                citations[k--] = 0;
                                citations[idx] = MSB + 2;
                            } else {
                                citations[k] = citations[idx];
    		                    citations[idx] = MSB + 1;
                            }
                        }
                    } else {
                        citations[k--] = 0;
                    }
                }
            }
            
            for (int k = n-1; k > 0; k--) {
                if (citations[k] >= k + 1) {
                    return (k + 1);
                } else {
                    citations[k - 1] += citations[k];
                }
            }
            return ((citations[0] >= 1) ? 1 : 0);
        }
    };
    

Log in to reply
 

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