🌕 274. H 指数

难度: 🌕

问题描述

---

解法 1 - 排序

class Solution {
    public int hIndex(int[] citations) {
        // 思路：
        // 数组排序 - 找到某个下标处 [len - i] >= i
        Arrays.sort(citations);
        int len = citations.length;
        int i = len;
        for(; i > 0; i --) {
            if(citations[len - i] >= i) {
                return i;
            }
        }
        return 0;
    }
}

---

输出 1

---

解法 2 - 二分

class Solution {
    public int hIndex(int[] citations) {
        // 思路：
        // 二分 - h ∈ [0, len]，从 len 开始往下查找
        int len = citations.length;
        return mySol(citations, 0, len);
    }

    private int mySol(int[] citations, int left, int right) {
        // 递归终止条件
        if(left >= right) {
            return left;
        }
        if(left == right - 1) {
            int tmp = 0;
            for(int i : citations) {
                if(i >= right) {
                    tmp ++;
                }
            }
            if(tmp >= right) {
                return right;
            } else {
                return left;
            }
        }
        int mid = left + ((right - left) >> 1);
        int count = 0;
        for(int i: citations) {
            if(i >= mid) {
                count ++;
            }
        }
        if(count >= mid) {
            return mySol(citations, mid, right);
        } else {
            return mySol(citations, left, mid - 1);
        }
    }
}

---

输出 2

---

解法 3

class Solution {
    public int hIndex(int[] citations) {
        // 思路：
        // h ∈ [0, len] 
        // 设置数组，记录 [0, len] 各次数下论文数量
        // 从后往前遍历非空下标，判断是否满足条件，若不满足条件，继续遍历
        int len = citations.length;
        int[] array = new int[len + 1];
        for(int i: citations) {
            if(i > len) {
                array[len] ++; // 超出 len 次数的论文按照 len 统计
            } else {
                array[i] ++;
            }
        }
        // 遍历 array
        int prev = 0; // 前面保存的论文数，这样就不用每次遇到一个可能的 h 值就进行数组的遍历统计有多少个比它大的数
        for(int j = len; j >= 0; j --) {
            prev += array[j];
            if(prev >= j) {
                return j;
            }
        }
        return 0;
    }
}

---

输出 3