274. H-Index

https://leetcode.com/problems/h-index/

題解

第一遍沒看懂題目。看了中文版的題目才明白，是要找到 h，滿足總共有 h 篇論文分別被引用了至少 h 次。

經過觀察發現，數組排序后，所謂“至少被引用了 h 次”，就是數組中大于等于 h 的數字的個數，也就是排序數組中 h 位置右邊的數字個數。

所以思路是，先對數組排序，排序后，反向下標遍歷數組，當下標首次 大于或等于 數組的值時，返回。其中：

• 等于，則返回 i
• 大于，則返回 i-1
  

代碼

class Solution {public int hIndex(int[] citations) {Arrays.sort(citations);int len = citations.length;for (int i = 1; i <= len; i++) {if (citations[len - i] == i) return i;else if (citations[len - i] < i) return i - 1;}return len;} }

275. H-Index II

https://leetcode.com/problems/h-index-ii/

題解

這題和上面的 I 題在定義上沒區別，只不過是提前幫你排好序，并且要求你在 logn 時間復雜度下完成。偷懶方法是，直接復制 I 題的代碼就可以了。但這不是出題人的目標。

• 題 I 無法在 O(logn) 時間復雜度下完成，是因為 排序的過程占大頭，至少是個 O(n*logn) 。題 I 當然也可以用二分查找來優化，但優化的只是低階的部分的復雜度，所以二分優化的意義不大。
• 題 II 直接把 排好序 的數組給你，目的就是為了 考察二分查找。

本題中，二分查找的目標，是找到 從前往后數，最后一個“下首次大于上” 的位置。

class Solution {public int hIndex(int[] citations) {int len = citations.length;int lo = 0;int hi = len - 1;int mid = (lo + hi) / 2;while (lo < hi) {if (citations[mid] <= len - mid) lo = mid + 1;else hi = mid;if (citations[lo] > len - lo) break; // 如果已經超出了符合“下首次大于上”條件的邊界，及時break，保留了最后一次有效的midmid = (lo + hi) / 2;}if (citations[mid] == len - mid) return len - mid;else if (citations[mid] < len - mid) return len - mid - 1;else return len;} }

最下面的 10:57 的提交記錄，是直接復制 I 題的代碼，相當于 O(n) 復雜度，也通過了。

后來才構思了二分查找的方式，邊界問題還是挺坑的，調了很長時間。

總結

以上是生活随笔為你收集整理的leetcode 274, 275. H-Index I, II（H 指数问题合集，线性查找/二分查找）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。