This article is participating in Python Theme Month. See the link for details

Topic describes

This is the 274.h index on LeetCode, which is of medium difficulty.

Tag: “Dichotomy”

Given an array of citations for a researcher’s paper (citations are non-negative integers). Write a method to calculate the researcher’s H-index.

The definition of h-index: H stands for “high citations”. A researcher’s H-index means that h of his or her papers have been cited at least H times. Each of the other N-H papers was cited no more than H times.

For example, if someone has an H-index of 20, that means they have 20 published papers that have been cited at least 20 times.

Example:

Input: citations = [3,0,6,1,5] Output: 3 Explanation: The given array means that the researcher has a total of 5 papers, and each paper has been cited 3,0,6,1,5 times accordingly. Since three of the researchers' papers were cited at least three times each, and the other two papers were cited no more than three times each, her H-index was 3.Copy the code

Tip: if h has multiple possible values, the h exponent is the largest of them.

Simulation + 2

We need to find the maximum XXX value in the condition “XXX papers cited at least XXX times”.

Then, on the positive integer number line with the maximum value XXX as the dividing point, the duality is satisfied:

  • Values less than or equal to XXX must satisfy the condition;
  • A value greater than XXX must not be satisfied.

Therefore, we can find the segmentation point XXX within the range of [0,n][0, n] by dichotomy.

Java code:

class Solution {
    public int hIndex(int[] cs) {
        int n = cs.length;
        int l = 0, r = n;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (check(cs, mid)) l = mid;
            else r = mid - 1;
        }
        return r;
    }
    boolean check(int[] cs, int mid) {
        int ans = 0;
        for (int i : cs) if (i >= mid) ans++;
        returnans >= mid; }}Copy the code

Python 3 code:

class Solution:
    def hIndex(self, citations: List[int]) - >int:
        def check(cs, mid) :
            return sum(i >= mid for i in cs) >= mid

        n = len(citations)
        l, r = 0, n
        while l < r:
            mid = l + r + 1 >> 1
            if check(citations, mid):
                l = mid
            else:
                r = mid - 1
        return r
Copy the code
  • Time complexity: Yes
    [ 0 . n ] [0, n]     Let’s do the dichotomy, and the complexity is zero
    O ( log ⁡ n ) O(\log{n})     ;checkThe function requires linear traversal of the array with the complexity of
    O ( n ) O(n)     . The overall complexity is
    O ( n log ⁡ n ) O(n\log{n})
  • Space complexity: O(1)O(1)O(1)

The last

This is No.274 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics in LeetCode as of the start date, some of which have locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.