Viiisit [LeetCode] - 274. H-Index

keep learning, keep coding!

Problem - H-Index

Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper, return the researcher’s h-index.

According to the definition of h-index on Wikipedia: The h-index is defined as the maximum value of h such that the given researcher has published at least h papers that have each been cited at least h times.

翻譯蒟蒻

本題旨在找出一位研究者的 h 指數，h 指數是指一位研究者的論文中至少有 h 篇被引用了至少 h 次，且其他論文被引用次數不超過 h。

• Example 1:

  Input: citations = [3,0,6,1,5]
  Output: 3
  Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 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.

• Example 2:

  Input: citations = [1,3,1]
  Output: 1

---

Solution - JavaScript

Solution 1:
(Runtime - 61ms)

var hIndex = function(citations) {
  citations.sort((a, b) => a - b);
  let h = 0;
  for (let i = 0; i < citations.length; i++) {
    if (citations[i] >= citations.length - i) {
      h = Math.max(h, citations.length - i)
    }
  }
  return h;
};

Solution 2:
(Runtime - 54ms)

/**
 * @param {number[]} citations
 * @return {number}
 */
var hIndex = function(citations) {
  citations.sort((a, b) => a - b);
  let h = 0;
  for (let i = citations.length - 1; i >= 0; i--) {
    if (citations[i] >= citations.length - i) {
      h = citations.length - i;
    }
  }
  return h;
};

• 過程：
  • citations.sort((a, b) => a - b)) 從小到大遍歷引用次數。
  • 用反向迴圈去找到最大的 h 指數，即找到最大的 i，滿足 citations[i] >= citations.length - i。
  • 判斷引用次數是否大於或等於 citations.length - i。這是因為 citations.length - i 表示從當前位置開始的剩餘論文數。如果引用次數足夠大，以至於至少有 citations.length - i 篇論文被引用了這麼多次，這樣就滿足了 h 指數的定義。
  • 如果滿足條件，更新 h 指數為 citations.length - i。

Solution - Ruby

Solution 1:

def h_index(citations)
    citations.sort!
    h = 0
    citations.each_with_index do |citation, i|
      if citation >= citations.length - i
        h = [h, citations.length - i].max
      end
    end
    h
end

Solution 2:

def h_index(citations)
    citations.sort!
    h = 0
    citations.reverse_each.with_index do |citation, i|
      if citation >= i + 1
        h = [h, i + 1].max
      end
    end
    h
end

LeetCode 傳送門 - H-Index