online advertising

Saturday, September 5, 2015

LeetCode OJ - H-Index

Problem:

Please find the problem here.

Solution:

The key observation is that the count is a monotonically decreasing sequence and one can represent it using differences.

For the example:

citations = [3, 0, 6, 1, 5]

the number of papers with more than i citations can be represented as follow

There is 2 paper with at least 5 citations
There is 2 paper with at least 4 citations
There is 3 papers with at least 3 citations
There is 3 papers with at least 2 citations
There is 4 papers with at least 1 citations

So we represent it as a 4 3 3 2 2 array - note that it is monotonically decreasing, so we can represent it using:

1 0 1 0 2

Now, let's work backwards, when we see the paper with 3 citations, we can populate the third (i.e. array index 2) element a 1, meaning we have 1 paper with at least 3 citations, and therefore we have implicitly 1 paper with at least k citation for all $ k \le 3 $. We can continue this trick and fill the array, compute the explicit number of citations using a running sum, and finally do the output.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/h-index/

#include "LEET_H_INDEX.h"
#include <stack>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_H_INDEX
{
    class Solution {
    public:
        int hIndex(vector<int>& citations)
        {
            if (citations.size() == 0)
            {
                return 0;
            }
            vector<int> counters;
            counters.resize(citations.size() + 1);
            for (unsigned int i = 0; i < citations.size() + 1; i++)
            {
                counters[i] = 0;
            }

            for (unsigned int i = 0; i < citations.size(); i++)
            {
                unsigned int cites = citations[i];
                if (cites > citations.size())
                {
                    cites = citations.size();
                }
                if (cites > 0)
                {
                    counters[cites - 1]++;
                }
            }

            for (unsigned int i = citations.size(); i > 0; i--)
            {
                counters[i - 1] = counters[i] + counters[i - 1];
                if (counters[i - 1] >= i)
                {
                    return i;
                }
            }

            return 0;
        }
    };
};

using namespace _LEET_H_INDEX;

int LEET_H_INDEX()
{
    int case1[] = { 3, 0, 6, 1, 5 };
    int case2[] = { 1 };
    int case3[] = { 1, 1 };
    Solution solution;
    cout << solution.hIndex(vector<int>(case3, case3 + _countof(case3))) << endl;
    return 0;
}

No comments :

Post a Comment