Published on

The Algorithm Design Manual (3rd) Exercise Solution 'E4-7'

Table of Contents

Introduction

This series is my solutions for algorithm exercises in'The Algorithm Design Manual' 3rd edition.
It's my solutions, not model answers, so if you find some mistakes or more sophisticated solutions, please post in comment area below.

Repository

Here

Exercise 4-7

Question

Give an efficient algorithm to take the array of citation counts (each count is a non-negative integer) of a researcher’s papers, and compute the researcher’s h-index. By definition, a scientist has index h if h of his or her n papers have been cited at least h times, while the other n−h papers each have no more than h citations.

Solution

Outline

First, sort the array in descending order.
Then, exanime from the head of the array whether the value of index i is greater than i. If not so, stop and return i-1.
Repeat it until the end of the array.

Code

// First, sort the array in descending order.
// Then, exanime from the head of the array
//  whether the value of index i is greater than i.
//  If not so, stop and return i-1.
// Repeat it until the end of the array.

#include <algorithm>
#include <cassert>
#include <vector>

int find_h_index(const std::vector<int>& citation_cnts) {
    std::vector<int> cp_cc(citation_cnts);
    std::sort(cp_cc.begin(), cp_cc.end(),
              [](auto& a, auto& b) { return a > b; });
    for (int i = 1; i <= static_cast<int>(cp_cc.size()); i++) {
        if (cp_cc[i - 1] < i) return i - 1;
    }
    return static_cast<int>(cp_cc.size());
}

int main(int argc, char const* argv[]) {
    assert(find_h_index({1}) == 1);
    assert(find_h_index({0}) == 0);
    assert(find_h_index({1, 1, 1, 1, 1, 1}) == 1);
    assert(find_h_index({6, 3, 9, 1, 3, 8}) == 3);
    assert(find_h_index({6, 3, 9, 1, 6, 8}) == 4);
    assert(find_h_index({9, 9, 9, 9, 9, 9}) == 6);
    assert(find_h_index({15, 33, 20, 30, 4, 5, 6, 7}) == 6);
    return 0;
}