O(n) solution


  • 1
    #include <vector>
    #include <stdio.h>
    #include <iostream>
    
    using namespace std;
    
    class Solution {
    public:
        int hIndex(vector<int>& citations) {
            int size = citations.size();
            int *cnt = new int[size + 1];
            for (int i = 0; i <= size; i++) {
                cnt[i] = 0;
            }
            int *aggr = new int[size + 1];
            for (int i = 0; i < size; i++) {
                int tmp = citations[i];
                if (tmp < size) {
                    cnt[tmp]++;
                } else {
                    cnt[size]++;
                }
            }
            aggr[size] = cnt[size];
            for (int i = size-1; i >= 0; i--) {
                aggr[i] = aggr[i+1] + cnt[i];
            }
            int low = 0, high = size, mid;
            while (low < high) {
                mid = (low + high) / 2;
                if (mid < aggr[mid] - cnt[mid]) {
                    low = mid + 1;
                } else if (mid > aggr[mid]) {
                    high = mid - 1;
                } else {
                    delete [] aggr;
                    delete [] cnt;
                    return mid;
                }
            }
            delete [] aggr;
            delete [] cnt;
            return low;
        }
    };
    
    int main() {
        Solution solution;
        vector<int> test;
        test.push_back(3);
        test.push_back(0);
        test.push_back(6);
        test.push_back(1);
        test.push_back(5);
        cout << solution.hIndex(test) << endl;
    }
    

Log in to reply
 

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