Saturday, September 5, 2015

LeetCode OJ - H-Index

Problem:

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;
}