12 line of C++ code, O(n), 0.00012s execution time!!! (3 solutions inside)


  • 1

    my best solution as described in the title

     class Solution {
        public:
            int cycle(vector<int>& citations){
                // there are 'flag' nums greater than 'ret + 1'
                int ret = 0, flag = 0, size = citations.size();
                int record[size + 1];
                memset(record, 0, sizeof(record));
                for (int i = 0; i < size; ++i){
                    int cur = citations[i];
                    if (cur >= size) record[size]++;
                    else record[cur] += 1;
                    if (cur <= ret) continue;
                    if (++flag < ret + 1) continue;
                    flag -= record[++ret];
                }
                return ret;
            }
        
            int hIndex(vector<int>& citations) {
                for (int i = 0; i < 99; ++i) cycle(citations);
                return cycle(citations);   
            }
        };
    

    Since the execution time is so fast, I wrap it with a 100 times cycle.
    While it still only needs 12ms time.

    several tips to consider:
    let's assume the total num of vector is 6

    1. the answer must be less than or equal 6.
    2. any number larger than 6 can be treated the same as 6.
    3. record 2 number: flag and ret. which means there are 'flag' nums greater than 'ret + 1'
    4. iterate the vector once, and the ret is what the solution is.

    ##here I provide another 2 solutions:

    second solution:

    the second solution is the same idea with the first but I use unordered_map, which takes much more time of 2.56ms:

    class Solution {
    public:
        int cycle(vector<int>& citations){
            // there are 'flag' nums greater than 'ret + 1'
            int ret = 0, flag = 0;
            unordered_map<int, int> uii;
            for (int i = 0; i < citations.size(); ++i){
                int cur = citations[i];
                uii[cur] += 1;
                if (cur <= ret) continue;
                if (++flag >= ret + 1){
                    ++ret;
                    flag -= uii[ret];
                }
            }
            return ret;
        }
    
        int hIndex(vector<int>& citations) {
            for (int i = 0; i < 99; ++i) cycle(citations);
            return cycle(citations);   
        }
    };
    

    the third solution:

    it sorts the vector first. time complexity of O(n*logn), it is faster than the second(1.16ms), amazing!

    class Solution {
    public:
        int cycle(vector<int>& citations){
            sort(citations.begin(), citations.end());
            int i = citations.size() - 1;
            for (; i >= 0; --i){
                int c = citations.size() - i;
                if (citations[i] < c) break;
            }
            return citations.size() - 1 -i;
        }
    
        int hIndex(vector<int>& citations) {
            for (int i = 0; i < 99; ++i) cycle(citations);
            return cycle(citations);   
        }
    };

  • 0
    T

    Hi, your algorithm1 is good! But a bit obscure to understand, at least to me. Based on your idea, I rewrote one with Bucket sorting, for easier reading for others.

    class Solution {
     public:
      int hIndex(vector<int>& citations) {
        auto size = int(citations.size());
        vector<int> buckets(size + 1);
    
        for (auto d: citations) {
          buckets[min(d, size)] += 1;
        }
    
        for (int p = size - 1; p >= 0; --p) {
          buckets[p] += buckets[p + 1]; 
        }
    
        int ret = 0;
        for (int p = size; p >= 0; --p) {
          ret = max(ret, min(p, buckets[p]));
        }
    
        return ret;
      }
    };
    

  • 0
    Y

    This one is a lot more friendly to me. Is it equivalent to original algorithm 1? For ret=max(ret, min(p, buckets[p])), do we have to loop from size to 0?


Log in to reply
 

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