LeetcodeのDaily Challengeはこの数ヶ月の間にやっていますが、
Qiitaで解答説明を投稿するのは初めてなんです。
もし役に立っていれば、ぜひ「いいね」やコメントをお願い致します。
今日の問題は：
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.
一応英語のままコピペしましたけど、意味分かりますよね。
まず、H-Indexを求めたいですね
H-Indexって何？一配列があって、中にX以上の数字の数がちょうどXになったとしたら、この配列のH-IndexはXと言いますね
目的が分かったら、次、どう解決しましょうね。
ヒントがあります。配列がすでにソートされていますね、気づきましたか？
ソートした配列に対して、まず「二分探索」を頭に思いつけてください
あと、ここに貼り付けていないですが、Follow Upのところにこう書いてあります：
•Could you solve it in logarithmic time complexity?
「対数の時間複雑度で解けますか？」言い換えれば、「二分探索」を使ってくださいという意味ですね。。
正直言って「二分探索」は難しいテーマですね、でもテンプレートあります：
int n = citations.length;
//まず、２ポインターを左右に配置
int left = 0;
int right = n - 1;
while(left <= right) {
int mid = left + (right - left) / 2;// 中点を取得
if(n - mid == citations[mid]) {// 見つけたら終わり
return n - mid;
} else if(n - mid > citations[mid]) {// 目標より小さいなら、左から絞る
left = mid + 1;
} else {// 目標より大きいなら、右から絞る
right = mid - 1;
}
}
return n - left;
二分探索はだいたいこんな感じですので、覚えてきたほうがいいです。
毎回問題によって変わったのはIF条件のところですね
今回の条件は、XとX以上の数字の数と合っているかどうか
X以上の数字の数って何だろう？ソートされたので、X右側の数字全部Xより大きくて、その数はXを含めて右にある要素数、いわゆる総数n - Xのインデックスですね
だから、条件はn - mid == citations[mid]) のように書けばいいです
最後迷うかもしれないことというと、left <= rightここにイコールをつけるかつけないかとの問題ですね
簡単に言うと、答えは配列以外にありえるか次第です、今回の場合、全部0だとしたら、H-Indexは0になってしまいます。だが、n - leftは0に届けないです！配列を超えてしまうので、イコールをつけないとエラー出ます。
解答と説明は以上となります。
初めてやったので、もし分からないこととか、間違っていたことがあったら、気軽に声をおかけください！