Leetcode – 274 – H index

[Blog link]

The path to learning at 🐔

The nuggets home page

[Topic Description

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. Tip: if h has multiple possible values, the h exponent is the largest of them. Related Topics Array Count sort sort 👍 192 👎 0Copy the code

[答 案]

Leetcode topic link

[making address]

Code link

[introduction]

Idea 1: Dichotomy

  • Because h cannot exceed the number of arrays, you can define values by binary lookup
  • Each time to determine whether the current h index is sufficient, if so, take the right half, otherwise take the left half
 class Solution {
        // Binary search
        // Since h cannot exceed the number of arrays, binary lookup can be used to define values
        // Each time to determine whether the current h index is sufficient, if so, take the right half, otherwise take the left half
        public int hIndex(int[] citations) {
            int n = citations.length;
            int l = 0, r = n ;
            while (l < r) {
                int cnt = 0, mid = (l - r + 1) / 2 + r;
                for (int nums : citations
                ) {
                    if (nums >= mid) {
                        cnt += 1; }}if (cnt >= mid) {
                    l = mid;
                } else {
                    r = mid - 1; }}returnr; }}Copy the code


Time complexity O ( n ∗ l g n ) Time complexity O(n*lg_{n})