No matter what everyone in the world says, I think my feelings are right. No matter what other people think, I never break my rhythm. Like things naturally can insist, do not like how also can not long.

LeetCode: the original address

Topic request

You are given an integer array of citations, where citations[I] represents the number of citations of the researcher’s i-th paper. Calculate and return the researcher’s H-index.

According to the Wikipedia h-index, where 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.

If there are multiple possible values for h, the h exponent is the largest of them.

Example 1:

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

Example 2:

Citations = [1,3,1] Output: 1Copy the code

Tip:

  • n == citations.length
  • 1 <= n <= 5000
  • 0 <= citations[i] <= 1000

Train of thought

Sort: quick sort or bucket sort

  • H = citations. Length-i, h = citations. I, h = citations
  • Restrictions to be met: Citations [I] >= h
  • Citations [I] >= citations. Length -i
  • Sort can be either quick sort or bucket sort
  • The time complexity is O(nlogn), and the space complexity is O(1), which applies to any data
  • The bucket sorting time complexity is O(n) and the space complexity is O(n). Citations [I] <= citations. Length

Search: Binary search

  • For traversal of sorted arrays, you can choose from left to right or binary search
  • Traverse from left to right
  • The minimum time complexity of the sorting part is O(n), so the search algorithm does not affect the final time complexity, and you can choose to traverse one by one from left to right
  • Binary search
  • The objective of binary search is to find the left margin of the second half
  • Citations [I] >= citations. Length – I
var hIndex = function (citations) {
    citations.sort((a, b) => a - b);
    let l = 0,
        r = citations.length - 1;
    while (l < r) {
        let m = l + r >> 1;
        if (citations[m] >= citations.length - m) r = m;
        else l = m + 1;
    }

    let h = citations.length - l;
    return citations[l] >= h ? h : 0;
};
Copy the code