LeetCode 275. H 指數(shù) II Java 實現(xiàn)與 274 的區(qū)別· 274citations 未排序可以排序或計數(shù)O(n log n) 或 O(n)。· 275citations 已經(jīng)按升序排列要求時間復(fù)雜度 O(log n)因此使用二分查找。二分思路數(shù)組升序設(shè) n citations.length。對于下標(biāo) mid· 從 mid 到末尾共有 n - mid 篇論文· 因為數(shù)組升序所以這 n - mid 篇論文的引用數(shù)都 ≥ citations[mid]· 如果 citations[mid] n - mid說明至少有 n - mid 篇論文引用數(shù) ≥ n - mid即 H 指數(shù)至少為 n - mid· 為了找最大的 H 指數(shù)我們需要讓 mid 盡量小因此滿足條件時繼續(xù)向左二分。最終 left 是第一個滿足條件的位置答案就是 n - left。Java 代碼classSolution{publicinthIndex(int[]citations){intncitations.length;intleft0,rightn-1;while(leftright){intmidleft(right-left)/2;// 從 mid 到末尾共有 n - mid 篇論文if(citations[mid]n-mid){// 滿足條件嘗試找更小的 mid以獲得更大的 hrightmid-1;}else{// 不滿足需要向右找leftmid1;}}// left 是第一個滿足條件的位置h n - leftreturnn-left;}}示例輸入citations [0,1,3,5,6]n 5步驟 left right mid citations[mid] n - mid 判斷1 0 4 2 3 3 3 3right 12 0 1 0 0 5 0 5 否left 13 1 1 1 1 4 1 4 否left 2結(jié)束 2 1 返回 5 - 2 3輸出3復(fù)雜度分析指標(biāo) 復(fù)雜度時間復(fù)雜度 O(log n)空間復(fù)雜度 O(1)關(guān)鍵點輸入已經(jīng)升序不要再次排序。n - mid 表示從 mid 到末尾的論文數(shù)量即當(dāng)前候選的 H 指數(shù)。二分找的是第一個滿足 citations[mid] n - mid 的位置這樣得到的 n - left 就是最大的 H 指數(shù)。邊界情況空數(shù)組可返回 0全為 0 返回 0[100] 返回 1。