java - 寻找 H 指数背后的直觉

Question

我在 LeetCode 上找到了以下代码片段可以有效地找出研究人员的 h 指数。维基百科定义 h-index如“一位科学家的索引为 h，如果他/她的 N 篇论文中有 h 篇每篇至少被引用 h 次，而其他 N − h 篇论文每篇被引用不超过 h 次。”

public class Solution {
    // 9.3 70 years diaoZhaTian China jiaYou 
    public int hIndex(int[] citations) {
        int length = citations.length;
        if (length == 0) {
            return 0;
        }

        int[] array2 = new int[length + 1];
        for (int i = 0; i < length; i++) {
            if (citations[i] > length) {
                array2[length] += 1;
            } else {
                array2[citations[i]] += 1;
            }
        }
        int t = 0;
        int result = 0;

        for (int i = length; i >= 0; i--) {
            t = t + array2[i];
            if (t >= i) {
                return i;
            }
        }
        return 0;
    }
}

虽然我理解第一个 for 循环的目的(计算各种引用的频率)，但第二个循环背后的直觉到底是什么？当累积和 (t) 大于或等于索引时，索引如何成为 h-index？

Answer 1

请注意，第二个循环是向下计数，而不是向上计数 - 因此累计总和是“至少有 i 次引用的论文数量”；因此，循环找到 i 的最大值，其中论文数量大于引用数量 - 这正是 h-index 的定义。