class Solution {
public:
int hIndex(vector<int>& citations) {
}
};
274. H 指数
给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。
根据维基百科上 h 指数的定义：h 代表“高引用次数”，一名科研人员的 h指数是指他（她）的 （n 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。且其余的 n - 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
提示：
n == citations.length1 <= n <= 50000 <= citations[i] <= 1000相似题目
原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 2.2 MB, 提交时间: 2023-10-29 10:29:03
func hIndex1(citations []int) (h int) {
sort.Ints(citations)
for i := len(citations) - 1; i >= 0 && citations[i] > h; i-- {
h++
}
return
}
func hIndex(citations []int) (h int) {
n := len(citations)
counter := make([]int, n+1)
for _, citation := range citations {
if citation >= n {
counter[n]++
} else {
counter[citation]++
}
}
for i, tot := n, 0; i >= 0; i-- {
tot += counter[i]
if tot >= i {
return i
}
}
return 0
}
func hIndex2(citations []int) int {
// 答案最多只能到数组长度
left,right:=0,len(citations)
var mid int
for left<right{
// +1 防止死循环
mid=(left+right+1)>>1
cnt:=0
for _,v:=range citations{
if v>=mid{
cnt++
}
}
if cnt>=mid{
// 要找的答案在 [mid,right] 区间内
left=mid
}else{
// 要找的答案在 [0,mid) 区间内
right=mid-1
}
}
return left
}
javascript 解法, 执行用时: 68 ms, 内存消耗: 42.3 MB, 提交时间: 2023-10-29 10:27:35
/**
* @param {number[]} citations
* @return {number}
*/
var hIndex = function(citations) {
let left = 0, right = citations.length
while (left<right){
// +1 防止死循环
let mid = Math.floor((left + right + 1) / 2)
let cnt = 0
for (let v of citations){
if (v >= mid){
cnt+=1
}
}
if(cnt>=mid){
// 要找的答案在 [mid,right] 区间内
left=mid
}else{
// 要找的答案在 [0,mid) 区间内
right=mid-1
}
}
return left
};
var hIndex2 = function(citations) {
let n = citations.length, tot = 0;
const counter = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) {
if (citations[i] >= n) {
counter[n]++;
} else {
counter[citations[i]]++;
}
}
for (let i = n; i >= 0; i--) {
tot += counter[i];
if (tot >= i) {
return i;
}
}
return 0;
};
var hIndex3 = function(citations) {
citations.sort((a, b) => a - b);
let h = 0, i = citations.length - 1;
while (i >= 0 && citations[i] > h) {
h++;
i--;
}
return h;
};
python3 解法, 执行用时: 44 ms, 内存消耗: 16.2 MB, 提交时间: 2023-10-29 10:26:49
class Solution:
def hIndex1(self, citations: List[int]) -> int:
sorted_citation = sorted(citations, reverse = True)
h = 0; i = 0; n = len(citations)
while i < n and sorted_citation[i] > h:
h += 1
i += 1
return h
# 计数排序
def hIndex(self, citations: List[int]) -> int:
n = len(citations); tot = 0
counter = [0] * (n+1)
for c in citations:
if c >= n:
counter[n] += 1
else:
counter[c] += 1
for i in range(n, -1, -1):
tot += counter[i]
if tot >= i:
return i
return 0
# 二分
def hIndex2(self, citations: List[int]) -> int:
left,right = 0,len(citations)
while left<right:
# +1 防止死循环
mid = (left+right+1)>>1
cnt = 0
for v in citations:
if v>=mid:
cnt+=1
if cnt>=mid:
# 要找的答案在 [mid,right] 区间内
left=mid
else:
# 要找的答案在 [0,mid) 区间内
right=mid-1
return left
cpp 解法, 执行用时: 0 ms, 内存消耗: 8.6 MB, 提交时间: 2023-10-29 10:25:37
class Solution {
public:
// 二分搜搜
int hIndex(vector<int>& citations) {
int left=0,right=citations.size();
int mid=0,cnt=0;
while(left<right){
// +1 防止死循环
mid=(left+right+1)>>1;
cnt=0;
for(int i=0;i<citations.size();i++){
if(citations[i]>=mid){
cnt++;
}
}
if(cnt>=mid){
// 要找的答案在 [mid,right] 区间内
left=mid;
}else{
// 要找的答案在 [0,mid) 区间内
right=mid-1;
}
}
return left;
}
// 计数排序
int hIndex1(vector<int>& citations) {
int n = citations.size(), tot = 0;
vector<int> counter(n + 1);
for (int i = 0; i < n; i++) {
if (citations[i] >= n) {
counter[n]++;
} else {
counter[citations[i]]++;
}
}
for (int i = n; i >= 0; i--) {
tot += counter[i];
if (tot >= i) {
return i;
}
}
return 0;
}
// 排序
int hIndex2(vector<int>& citations) {
sort(citations.begin(), citations.end());
int h = 0, i = citations.size() - 1;
while (i >= 0 && citations[i] > h) {
h++;
i--;
}
return h;
}
};
java 解法, 执行用时: 1 ms, 内存消耗: 39.1 MB, 提交时间: 2023-10-29 10:24:22
class Solution {
public int hIndex(int[] citations) {
Arrays.sort(citations);
int h = 0, i = citations.length - 1;
while (i >= 0 && citations[i] > h) {
h++;
i--;
}
return h;
}
// 计数排序
public int hIndex1(int[] citations) {
int n = citations.length, tot = 0;
int[] counter = new int[n + 1];
for (int i = 0; i < n; i++) {
if (citations[i] >= n) {
counter[n]++;
} else {
counter[citations[i]]++;
}
}
for (int i = n; i >= 0; i--) {
tot += counter[i];
if (tot >= i) {
return i;
}
}
return 0;
}
// 二分搜索
public int hIndex2(int[] citations) {
int left=0,right=citations.length;
int mid=0,cnt=0;
while(left<right){
// +1 防止死循环
mid=(left+right+1)>>1;
cnt=0;
for(int i=0;i<citations.length;i++){
if(citations[i]>=mid){
cnt++;
}
}
if(cnt>=mid){
// 要找的答案在 [mid,right] 区间内
left=mid;
}else{
// 要找的答案在 [0,mid) 区间内
right=mid-1;
}
}
return left;
}
}
python3 解法, 执行用时: 44 ms, 内存消耗: 15.1 MB, 提交时间: 2022-07-12 17:30:46
class Solution:
def hIndex(self, citations: List[int]) -> int:
citations = sorted(citations, reverse=True)
h = 0
i = 0
n = len(citations)
while i < n and citations[i] > h:
i += 1
h += 1
return h