### 包子小道消息@12/07/2019

从growth at all cost 到profitability mindset，都是被Uber Wework 弄得。软银老板Masa的头发估计又得脱落几根，不过airbnb也许是2020年被大家追捧的一个新星，从cash at hand / total funds raised 的比例来看，就是下一个google，Facebook和zoom的节奏啊！

### Problem Statement

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.

According to the definition of h-index on Wikipedia: "A scientist has index

*h*if*h*of his/her*N*papers have**at least***h*citations each, and the other*N − h*papers have**no more than***h*citations each."**Example:**

Input:`citations = [3,0,6,1,5]`

Output:3Explanation:`[3,0,6,1,5]`

means the researcher has`5`

papers in total and each of them had received`3, 0, 6, 1, 5`

citations respectively. Since the researcher has`3`

papers withat least`3`

citations each and the remaining two withno more than`3`

citations each, her h-index is`3`

.

**Note:**If there are several possible values for

*h*, the maximum one is taken as the h-index.

*Hint 1*

*An easy approach is to sort the array first.*

*Hint 2*

What are the possible values of h-index?

What are the possible values of h-index?

*Hint 3*

A faster approach is to use extra space.

A faster approach is to use extra space.

Problem link

### Video Tutorial

You can find the detailed video tutorial here### Thought Process

It’s not the most straightforward question to understand I have to admit that. I normally start with small examples to help me understandThe requirement is: his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each

What happens if citation contains only 1 element?

- Citations = [100] , N = 1, h = 1, N-h = 0

What happens if citation contains only 2 elements? And we can assign some large citation values

- Citations = [1000, 2000] , N = 2, h = 2. It seems h-index has not too much to do with the citation values itself, rather it’s about the index and the values.

We should now have a super brute force way, since h is bounded to be [0, N], we just go through each value and try to see if it could meet the h criteria (e.g., we start from N, then we see if there is at least N papers that have at least N citations) This would result in a O(N^2) time complexity.

Naturally, we normally can think of if we can sort the array to reduce the time complexity. After sort, using the below graph, the problem becomes find the citation more than the citation array index, and that citation index could be the h-index (that's why it's called h-index, not h-value, it's about index). This would give a O(NlgN) time complexity. Code is attached in the References section.

source: leetcode solution |

Finally, we can think about bucket sort since h-index is bounded from [0, N], and if paper citations are larger than N, it's just considered on counting on index N.

You know how to do a bucket sort 😄

### Solutions

#### Use bucket sort

Time Complexity: O(N) since we went through citations only onceSpace Complexity: O(N) since we are using an extra array to keep track of the count

### References

- Leetcode official solution (download pdf)

## No comments:

## Post a Comment

Thank your for your comment! Check out us at https://baozitraining.org/ if you need mock interviews!