leetcode 274, 275. H-Index I, II（H 指数问题合集，线性查找/二分查找）

迈不过友情╰ 2022-10-11 00:45 223阅读 0赞

## 274. H-Index ##

[https://leetcode.com/problems/h-index/][https_leetcode.com_problems_h-index]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

#### 题解 ####

第一遍没看懂题目。看了中文版的题目才明白，是要找到 h，满足总共有 h 篇论文分别被引用了至少 h 次。

经过观察发现，数组排序后，所谓“至少被引用了 h 次”，就是数组中大于等于 h 的数字的个数，也就是排序数组中 h 位置右边的数字个数。

所以思路是，先对数组排序，排序后，反向下标遍历数组，当下标首次 **大于或等于** 数组的值时，返回。其中：

*  等于，则返回 i
 *  大于，则返回 i-1  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]

#### 代码 ####

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;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

## 275. H-Index II ##

[https://leetcode.com/problems/h-index-ii/][https_leetcode.com_problems_h-index-ii]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]

#### 题解 ####

这题和上面的 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，保留了最后一次有效的mid
                mid = (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) 复杂度，也通过了。

后来才构思了二分查找的方式，边界问题还是挺坑的，调了很长时间。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 3]

[https_leetcode.com_problems_h-index]: https://leetcode.com/problems/h-index/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221005/9c4790043ffb46028c93feb5cd9a2db5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20221005/48ab7a04149d4304acd92e5176767a76.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20221005/b62b30a68cde44e1bf22d5f30783fd9c.png
[https_leetcode.com_problems_h-index-ii]: https://leetcode.com/problems/h-index-ii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]: /images/20221005/9b453f66d23947d7b033016f1e799e45.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 3]: /images/20221005/3266730a793d4527a66228c16891a86e.png