mirror of
https://github.com/ShusenTang/LeetCode.git
synced 2024-09-02 14:20:01 +00:00
24 lines
930 B
Markdown
24 lines
930 B
Markdown
|
# [275. H-Index II](https://leetcode.com/problems/h-index-ii/)
|
|||
|
|
# 思路
|
|||
|
|
这题实际上是[274. H-Index](https://leetcode.com/problems/h-index/)的简化版，274题引用列表没有排好序此题已经排序了。
|
|||
|
|
所以会做274题的话此题肯定没问题，[274题思路二](https://github.com/ShusenTang/LeetCode/blob/master/solutions/274.%20H-Index.md)其实就和此题的解法类似，复杂度为O(logn)，这里不再赘述。
|
|||
|
|
|
|||
|
|
# C++
|
|||
|
|
``` C++
|
|||
|
|
class Solution {
|
|||
|
|
public:
|
|||
|
|
int hIndex(vector<int>& citations) {
|
|||
|
|
int n = citations.size();
|
|||
|
|
if(!n) return 0;
|
|||
|
|
int left = 0, right = n - 1;
|
|||
|
|
while(left < right){
|
|||
|
|
int mid = (left + right) >> 1;
|
|||
|
|
if(n - mid == citations[mid]) return citations[mid];
|
|||
|
|
if(n - mid > citations[mid]) left = mid + 1;
|
|||
|
|
else right = mid;
|
|||
|
|
}
|
|||
|
|
return min(citations[left], n - left); // left == right
|
|||
|
|
}
|
|||
|
|
};
|
|||
|
|
```
|