**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