План курса / Все задачи / Алгоритмы и структуры данных
Индекс Хирша
сложно
# решено
Дан массив целых чисел citations, где citations[i] — число цитирований, полученных исследователем для его i-й статьи. Нужно найти h-индекс исследователя.
H-индекс (индекс Хирша) определяется как максимальное значение h, при котором данный исследователь опубликовал не менее h статей, каждая из которых была процитирована не менее h раз.
Пример 1:
Ввод: citations=[10,1,8,0,3]
Вывод: 3
Объяснение: есть 3 статьи, которые были процитированы >= 3 раз (для 4 уже нет)
Пример 2:
Ввод: citations=[100,200]
Вывод: 2
Объяснение: есть 2 статьи, которые были процитированы >= 2 раз
Ограничения:
citations[i] >= 0
len(citations) >= 1
public class Solution
{
// Функция для вычисления индекса Хирша
public static int FindHirschIndex(List<int> citations)
{
int n = citations.Count;
// Индекс — число цитирований, а значение — количество статей
// с таким количеством цитирований
List<int> buckets = new List<int>(new int[n + 1]);
foreach (int citation in citations)
{
if (citation >= n)
{
// При citation >= n можем увеличивать число статей
// только последнего бакета, потому что для последовательности
// из n статей индекс Хирша максимум n
buckets[n]++;
}
else
{
buckets[citation]++;
}
}
int count = 0;
// Перебираем значения от максимального возможного индекса n к 0,
// чтобы найти наибольший индекс i,
// где количество статей с цитированием >= i
for (int i = n; i >= 0; i--)
{
count += buckets[i];
if (count >= i)
{
// Если число таких статей больше или равно текущему i,
// это и есть индекс Хирша
return i;
}
}
return 0;
}
}
#include <vector>
using namespace std;
int findHirschIndex(vector<int>& citations) {
int n = citations.size();
// Индекс — число цитирований, а значение — количество статей
// с таким количеством цитирований
vector<int> buckets(n + 1, 0);
for (int citation : citations) {
if (citation >= n) {
// При citation >= n можем увеличивать число статей
// только последнего бакета, потому что для последовательности
// из n статей индекс Хирша максимум n
buckets[n]++;
} else {
buckets[citation]++;
}
}
int count = 0;
// Перебираем значения от максимального возможного индекса n к 0,
// чтобы найти наибольший индекс i,
// где количество статей с цитированием >= i
for (int i = n; i >= 0; i--) {
count += buckets[i];
if (count >= i) {
// Если число таких статей больше или равно текущему i,
// это и есть индекс Хирша
return i;
}
}
return 0;
}
package main;
func findHirschIndex(citations []int) int {
n := len(citations)
// Индекс — число цитирований, а значение — количество статей
// с таким количеством цитирований
buckets := make([]int, n+1)
for _, citation := range citations {
if citation >= n {
// При citation >= n можем увеличивать число статей
// только последнего бакета, потому что для последовательности
// из n статей индекс Хирша максимум n
buckets[n]++
} else {
buckets[citation]++
}
}
count := 0
// Перебираем значения от максимального возможного индекса n к 0,
// чтобы найти наибольший индекс i,
// где количество статей с цитированием >= i
for i := n; i >= 0; i-- {
count += buckets[i]
if count >= i {
// Если число таких статей больше или равно текущему i,
// это и есть индекс Хирша
return i
}
}
return 0
}
import java.util.*;
public class Solution {
public int findHirschIndex(List<Integer> citations) {
int n = citations.size();
// Индекс — число цитирований, а значение — количество статей
// с таким количеством цитирований
int[] buckets = new int[n + 1];
for (int citation : citations) {
if (citation >= n) {
// При citation >= n можем увеличивать число статей
// только последнего бакета, потому что для последовательности
// из n статей индекс Хирша максимум n
buckets[n]++;
} else {
buckets[citation]++;
}
}
int count = 0;
// Перебираем значения от максимального возможного индекса n к 0,
// чтобы найти наибольший индекс i,
// где количество статей с цитированием >= i
for (int i = n; i >= 0; i--) {
count += buckets[i];
if (count >= i) {
// Если число таких статей больше или равно текущему i,
// это и есть индекс Хирша
return i;
}
}
return 0;
}
}
from typing import *
def find_hirsch_index(citations):
n = len(citations)
# Индекс — число цитирований, а значение — количество статей
# с таким количеством цитирований
buckets = [0] * (n + 1)
for citation in citations:
if citation >= n:
# При citation >= n можем увеличивать число статей
# только последнего бакета, потому что для последовательности
# из n статей индекс Хирша максимум n
buckets[n] += 1
else:
buckets[citation] += 1
count = 0
# Перебираем значения от максимального возможного индекса n к 0,
# чтобы найти наибольший индекс i,
# где количество статей с цитированием >= i
for i in range(n, -1, -1):
count += buckets[i]
if count >= i:
# Если число таких статей больше или равно текущему i,
# это и есть индекс Хирша
return i
return 0
export function findHirschIndex(citations) {
const n = citations.length;
// Индекс — число цитирований, а значение — количество статей
// с таким количеством цитирований
const buckets = new Array(n + 1).fill(0);
for (const citation of citations) {
if (citation >= n) {
// При citation >= n можем увеличивать число статей
// только последнего бакета, потому что для последовательности
// из n статей индекс Хирша максимум n
buckets[n]++;
} else {
buckets[citation]++;
}
}
let count = 0;
// Перебираем значения от максимального возможного индекса n к 0,
// чтобы найти наибольший индекс i,
// где количество статей с цитированием >= i
for (let i = n; i >= 0; i--) {
count += buckets[i];
if (count >= i) {
// Если число таких статей больше или равно текущему i,
// это и есть индекс Хирша
return i;
}
}
return 0;
}