275. H-Index II

LeetCode medium original: C# #array #backtracking #csharp #hash-table #leetcode #medium #search #sort #two-pointers

Task text is translated from Russian for the selected interface language. Code is left unchanged.

LeetCode Static

Дан array целых чисел citations, где citations[i] — количество цитирований, которое исследователь получил за свою i-ю статью, и array отсортирован в порядке возрастания. return h-индекс исследователя.

Согласно определению h-индекса на Википедии: h-индекс определяется как максимальное значение h, такое что данный исследователь опубликовал по крайней мере h статей, каждая из которых была процитирована как минимум h раз.

C# solution

matched/original

public class Solution {
    public int HIndex(int[] citations) {
        int n = citations.Length;
        int left = 0, right = n - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (citations[mid] == n - mid) {
                return n - mid;
            } else if (citations[mid] < n - mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return n - left;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int HIndex(vector<int>& citations) {
        int n = citations.size();
        int left = 0, right = n - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (citations[mid] == n - mid) {
                return n - mid;
            } else if (citations[mid] < n - mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return n - left;
    }
}

Java solution

matched/original

public class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int left = 0, right = n - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (citations[mid] == n - mid) {
                return n - mid;
            } else if (citations[mid] < n - mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return n - left;
    }
}

JavaScript solution

matched/original

var hIndex = function(citations) {
    let n = citations.length;
    let left = 0, right = n - 1;
    
    while (left <= right) {
        let mid = left + Math.floor((right - left) / 2);
        if (citations[mid] === n - mid) {
            return n - mid;
        } else if (citations[mid] < n - mid) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return n - left;
};

Python solution

matched/original

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        n = len(citations)
        left, right = 0, n - 1
        
        while left <= right:
            mid = left + (right - left) // 2
            if citations[mid] == n - mid:
                return n - mid
            elif citations[mid] < n - mid:
                left = mid + 1
            else:
                right = mid - 1
        
        return n - left

Go solution

matched/original

func hIndex(citations []int) int {
    n := len(citations)
    left, right := 0, n - 1
    
    for left <= right {
        mid := left + (right - left) / 2
        if citations[mid] == n - mid {
            return n - mid
        } else if citations[mid] < n - mid {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return n - left
}

Algorithm

Example:

Input: citations = [0,1,3,5,6]

Output: 3

Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had received 0, 1, 3, 5, 6 citations respectively.

Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.

👨‍💻

Algorithm:

1️⃣

find середину arrayа:

Определить средний element arrayа, чтобы разделить его на две подмножества: citations[0: mid - 1] и citations[mid + 1: n].

2️⃣

Сравнить количество статей с цитированиями больше или равными citations[mid]:

Если citations[mid] == n - mid, то найден h-индекс и его можно вернуть.

Если citations[mid] < n - mid, то необходимо искать в правой подмножности citations[mid + 1: n].

Если citations[mid] > n - mid, то необходимо искать в левой подмножности citations[0: mid - 1].

3️⃣

Возвращение результата:

Продолжать процесс, пока не будет найден h-индекс.

Возвратить n - mid, что является количеством статей с цитированиями больше или равными citations[mid].

😎

Vacancies for this task

Active vacancies with overlapping task tags are shown.

All vacancies

There are no active vacancies yet.