一、題目分析

（一）問題描述

給定一個整數數組 citations，其中 citations[i] 表示研究者的第 i 篇論文被引用的次數。我們需要計算并返回該研究者的 H 指數。根據維基百科定義：H 指數代表“高引用次數”，一名科研人員的 H 指數是指他（她）至少發表了 h 篇論文，并且至少有 h 篇論文被引用次數大于等于 h 。如果有多個可能的 h 值，取最大的那個。

比如，若有論文引用次數數組為 [3,0,6,1,5]，經過計算其 H 指數是 3，因為有 3 篇論文（引用次數為 3、6、5 ）的引用次數大于等于 3 。

（二）核心目標

遍歷處理論文引用次數數組，找到最大的 h 值，滿足存在至少 h 篇論文的引用次數 ≥ h 。

二、算法思想：排序 + 線性遍歷（貪心思想的體現）

（一）排序的作用

首先對 citations 數組進行排序（升序排序 ）。排序之后，數組的順序能夠幫助我們更方便地找到符合 H 指數定義的那個 h 值。升序排序后，數組后面的元素值相對較大，我們可以從后往前或者從前往后，利用數組的有序性來判斷滿足條件的 h 。

（二）線性遍歷與貪心策略

排序完成后，進行線性遍歷。我們的貪心策略是：從數組的一端開始，尋找滿足“存在 h 篇論文引用次數 ≥ h”這一條件的最大 h 。具體來說，對排序后的數組，我們從前往后遍歷，對于索引 i ，考慮以 n - i 作為可能的 h 值（n 是數組長度，也就是論文的總篇數 ），判斷當前論文的引用次數 citations[i] 是否大于等于 n - i 。一旦找到第一個滿足該條件的 i ，那么 n - i 就是我們要找的最大 H 指數。這是因為數組是升序排列的，后面的元素值更大，當在某個位置滿足條件后，繼續往后遍歷得到的 n - i 會更小，所以第一個滿足條件的 n - i 就是最大的符合要求的 H 指數，這體現了貪心算法中“找到第一個滿足局部條件就能得到全局最優”的思想 。

三、代碼實現及詳細注釋

import java.util.Arrays;class Solution {public int hIndex(int[] citations) {// 第一步：對引用次數數組進行升序排序Arrays.sort(citations);int n = citations.length; // 獲取論文的總篇數，也就是數組的長度for (int i = 0; i < n; i++) { // 對于當前索引i，考慮h值為n - i。這里的含義是：// 假設h是n - i，那么需要至少有n - i篇論文的引用次數≥h// 由于數組是升序排序的，citations[i]及后面的元素是較大的，當citations[i] >= n - i時，// 說明從i到n - 1位置的這n - i篇論文的引用次數都 >= citations[i]（因為升序），也就 >= n - iif (citations[i] >= n - i) { return n - i; // 找到滿足條件的最大h值，直接返回}}return 0; // 如果遍歷完都沒有滿足條件的，說明H指數為0（比如所有論文引用次數都為0的情況 ）}
}

（一）代碼執行流程詳解

1. 排序操作：

Arrays.sort(citations);

這行代碼使用 Java 內置的 Arrays.sort 方法對 citations 數組進行升序排序。例如，對于輸入數組 [3,0,6,1,5]，排序后會變成 [0,1,3,5,6] 。排序的時間復雜度為 $O(n\log n)$ ，其中 n 是數組的長度，這是由排序算法的時間復雜度決定的（Java 中 Arrays.sort 對于基本數據類型數組采用的是優化的快速排序等算法，平均時間復雜度為 $O(n\log n)$ ）。

2. 遍歷判斷過程：

int n = citations.length; 
for (int i = 0; i < n; i++) { if (citations[i] >= n - i) { return n - i; }
}

• 首先獲取數組長度 n ，代表論文的總篇數。
• 然后進入循環遍歷，i 從 0 開始遞增到 n - 1 。對于每一個 i ，計算 n - i ，這個值代表的是假設的 h 值，含義是當前考慮有 n - i 篇論文可能滿足引用次數 ≥ n - i 。
• 因為數組是升序排序的，citations[i] 是第 i + 1 小的引用次數（數組索引從 0 開始 ），當 citations[i] >= n - i 時，說明從第 i 篇論文開始（包括第 i 篇 ），后面一共有 n - i 篇論文（索引從 i 到 n - 1 ），它們的引用次數都大于等于 citations[i] ，自然也大于等于 n - i （因為 citations[i] >= n - i 且數組升序 ）。所以此時 n - i 就是滿足條件的 H 指數，直接返回即可。這是因為我們是從前往后遍歷，一旦找到第一個滿足條件的 i ，對應的 n - i 就是最大的可能的 H 指數。比如排序后的數組 [0,1,3,5,6] ，n = 5 ，當 i = 2 時，n - i = 3 ，citations[2] = 3 ，滿足 citations[i] >= n - i ，所以返回 3 ，也就是正確的 H 指數。

3. 返回默認值：

return 0; 

如果循環遍歷結束后，沒有找到滿足 citations[i] >= n - i 的情況，說明所有論文的引用次數都非常低，比如數組全為 0 ，此時 H 指數為 0 ，所以返回 0 。

四、算法的時間復雜度和空間復雜度分析

（一）時間復雜度

• 排序操作的時間復雜度：使用 Arrays.sort 對數組進行排序，其時間復雜度為 $O(n\log n)$ ，其中 n 是數組 citations 的長度。
• 線性遍歷的時間復雜度：排序后進行的線性遍歷，時間復雜度為 $O(n)$ ，n 同樣是數組長度。

所以，整個算法的時間復雜度由排序操作主導，為 $O(n\log n)$ 。

（二）空間復雜度

• 排序操作在 Java 中，對于基本數據類型數組的 Arrays.sort 方法，采用的是原地排序（大部分情況下 ），不需要額外的大量空間，空間復雜度為 $O(\log n)$ （主要是排序過程中遞歸調用棧或者用于輔助排序的空間，基于快速排序等算法的實現 ）。
• 其他變量如 n 、i 等都是常數級別的空間占用。

所以，整個算法的空間復雜度為 $O(\log n)$ （主要由排序操作決定 ），在大多數情況下可以認為是較為高效的空間利用。