1、題目：

給你一個整數數組 citations ，其中 citations[i] 表示研究者的第 i 篇論文被引用的次數。計算并返回該研究者的 h 指數。

根據維基百科上 h 指數的定義：h 代表“高引用次數” ，一名科研人員的 h 指數 是指他（她）至少發(fā)表了 h 篇論文，并且每篇論文 至少 被引用 h 次。如果 h 有多種可能的值，h 指數 是其中最大的那個。

2、分析特點：

• 題目要求：尋找最大值，citations[i] 表示研究者的第 i 篇論文被引用的次數 ==> 排序之后，使用二分法.
• 二分法使用常見場景 ==> 搜索有序列表：當你需要在一個有序列表（如數組）中查找某個特定元素時，可以使用二分法.

3、代碼：

class Solution {
    public int hIndex(int[] citations) {
        int left=0,right=citations.length;
        int mid=0,cnt=0;
        while(left<right){
            // +1 防止死循環(huán)
            mid=(left+right+1)>>1;
            cnt=0;
            for(int i=0;i<citations.length;i++){
                if(citations[i]>=mid){
                    cnt++;
                }
            }
            if(cnt>=mid){
                // 要找的答案在 [mid,right] 區(qū)間內
                left=mid;
            }else{
                // 要找的答案在 [0,mid) 區(qū)間內
                right=mid-1;
            }
        }
        return left;
    }
}

4、復雜度分析：

• 時間復雜度：O(nlogn)，其中 n 為數組 citations 的長度。需要進行 logn 次二分搜索，每次二分搜索需要遍歷數組 citations 一次。
  空間復雜度：O(1)，只需要常數個變量來進行二分搜索。

5、總結：

二分法使用常見場景 ==> 搜索有序列表：當你需要在一個有序列表（如數組）中查找某個特定元素時，可以使用二分法.

6、其他解決方法：排序法

解題思路：升序后判斷當前的數是否大于其對應的h值就行了

■ 代碼：

import java.util.Arrays;

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

如果本文對你有幫助的話記得給一樂點個贊哦，感謝！文章來源地址http://www.zghlxwxcb.cn/news/detail-718824.html

到了這里，關于算法：二分法---尋找H指數的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！