🌕 275. H 指数 II

难度: 🌕

问题描述

---

解法

class Solution {
    public int hIndex(int[] citations) {
        // 思路：
        // 二分，找到最大的 h，使得 [len - h] >= h
        // 即，找到最小的 i，使得 [i] >= len - i, h = len - i
        int len = citations.length;
        if(citations[len - 1] == 0) {
            return 0;
        }
        int i = mySol(citations, 0, len);
        return len - i;
    }

    private int mySol(int[] array, int left, int right) {
        // 递归终止条件
        int len = array.length;
        if(left >= right) {
            if(array[left] >= len - left) {
                return left;
            } else {
                return left + 1;
            }
        }
        if(left == right - 1) {
            if(array[left] >= len - left) {
                return left;
            } else if(array[right] >= len - right){
                return right;
            } else {
                return right + 1;
            }
        }
        
        int mid = left + ((right - left) >> 1);
        if(array[mid] >= len - mid) {
            return mySol(array, left, mid);
        } else {
            return mySol(array, mid + 1, right);
        }
    }
}

---

输出