一. 簡介

本文記錄力扣網上涉及數組，排序方面的編程題：H指數。

二.?力扣網編程274題：H指數（中等）

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

示例 1：
輸入：citations = [3,0,6,1,5]
輸出：3?
解釋：給定數組表示研究者總共有 5 篇論文，每篇論文相應的被引用了 3, 0, 6, 1, 5 次。
? ? ?由于研究者有 3 篇論文每篇 至少 被引用了 3 次，其余兩篇論文每篇被引用 不多于 3 次，所以她的 h 指數是 3。

示例 2：
輸入：citations = [1,3,1]
輸出：1

解題思路一：（排序后統計）

題目是尋找最大的 h，使得至少有 h 篇論文被引用 ≥h 次。

首先，對數組進行降序排序，即從大到小排序；

其次，從左向右遍歷數組，如果?citations[i]? > h 時，說明至少有 h+1篇文章引用次數 >= (h+1)，因此可以安全的將 h自增1；

最后返回 h即為指數。

這種方法利用了排序后的特性：

當遍歷到第 i 篇論文時，前面已經有 i 篇論文的引用次數 ≥ citations[i]。

如果?citations[i]? > h 時，說明至少有 h+1篇文章引用次數 >= (h+1)。

可以這里理解上面的特性：

? ? citations[i]：當遍歷到第i個元素值citations[i]，表示前 i+1 篇論文的引用次數 ≥ citations[i]（降序數組的特性）。
? ? citations[i] > h，因此：
? ? 前 i+1 篇論文的引用次數必然都 > h（因為它們 ≥ citations[i] > h）。
? ? 此時，至少有 i+1 篇論文的引用次數 > h，即：
? ? 至少有 i+1 篇論文的引用次數 ≥ h+1。

? ? 如果 i+1 ≥ h+1（即當前遍歷到的論文數量足夠），則說明：
? ? 存在 h+1 篇論文的引用次數 ≥ h+1，因此 H 指數可以更新為 h+1。

舉例說明：

舉個例子：如果某人有 5 篇論文，引用次數是 [3, 0, 6, 1, 5]，排序后為[6,5,3,1,0]
從前往后看：第 1 篇（6）≥ 1 → 至少有 1 篇 ≥ 1第 2 篇（5）≥ 2 → 至少有 2 篇 ≥ 2第 3 篇（3）≥ 3 → 至少有 3 篇 ≥ 3第 4 篇（1）< 4 → 不滿足 4 篇 ≥ 4

具體方法如下：

1. 首先初始化一個變量：h=0，來統計指數；

2. 其次，從大到小進行排序；

3. 從前往后遍歷數組，判斷 citations[i] > h，當滿足時，h自增1。

4.循環退出，最后的 h即所求的指數；

C語言實現如下：

//從大到小排序
int small_to_large(const void* a, const void* b) {return *(int*)b- *(int*)a;
}int hIndex(int* citations, int citationsSize) {int i;int h = 0;qsort(citations, citationsSize, sizeof(int), small_to_large);for(i = 0; i < citationsSize; i++) {if(citations[i] > h) {h++;}}return h;
}

可以看出，排序解法的時間復雜度為 O (n log n)。

下一篇文章使用計數排序解法進行處理：

力扣網編程274題：H指數之計數排序（中等）-CSDN博客