Leetcode's Daily Challenge has been going on in the last few months This is the first time I have posted an answer explanation on Qiita. If you find it useful, please like and comment.
Today's problem is:
H-Index II
Given an array of citations sorted in ascending order (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 = [0,1,3,5,6] Output: 3 Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had received 0, 1, 3, 5, 6 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, her h-index is 3.
I copied it in English for the time being, but you can understand the meaning.
First, I want to find the H-Index What is the H-Index? If you have an array and the number of numbers greater than or equal to X is exactly X, then the H-Index of this array is called X.
Once you know the purpose, how should you solve it next? I have a hint. Did you notice that the array is already sorted? For a sorted array, first think of "binary search"
Also, I haven't pasted it here, but it says in Follow Up:
•Could you solve it in logarithmic time complexity?
"Can you solve with logarithmic time complexity?" In other words, use "binary search". ..
To be honest, "binary search" is a difficult subject, but there is a template:
int n = citations.length;
//First, place 2 pointers left and right
int left = 0;
int right = n - 1;
while(left <= right) {
int mid = left + (right - left) / 2;//Get midpoint
if(n - mid == citations[mid]) {//If you find it, it's over
return n - mid;
} else if(n - mid > citations[mid]) {//If it is smaller than the target, squeeze from the left
left = mid + 1;
} else {//If it is larger than the target, squeeze from the right
right = mid - 1;
}
}
return n - left;
Binary search is like this, so you should remember it. It is the IF condition that changed depending on the problem every time.
Whether this condition meets ** X ** and the number of numbers ** X and above **
** What is the number of numbers above X ? Since it is sorted, all the numbers on the right side of X are larger than X, and the number is the number of elements on the right including X, so-called total number n- index of X **.
So the condition should be written as n --mid == citations [mid])
The last thing you might be wondering about is left <= right, the question is whether to add equality here or not.
Simply put, the answer depends on what could be other than an array. In this case, if all were 0, the H-Index would be 0. But n --left doesn't reach 0! Since it exceeds the array, an error will occur if you do not add equality.
That is all for the answer and explanation. I did it for the first time, so if you have any questions or mistakes, please feel free to contact me!