[LeetCode]H-Index II | 书影博客

[LeetCode]H-Index II | 书影博客
Follow up for H-Index: What if the citations array is sorted in ascending order? Could you optimize your algorithm?
Hint:
Expected runtime complexity is in O(log n) and the input is sorted.

H-Index的延伸：如果引用数组是递增有序的，你应该怎样优化算法？
提示：
期望运行时间复杂度为O(log n)，并且输入是递增有序的。

二分法（Binary Search）

http://www.cnblogs.com/grandyang/p/4782695.html

这题是之前那道H-Index 求H指数的拓展，输入数组是有序的，让我们在O(log n)的时间内完成计算，看到这个时间复杂度，应该有很敏锐的意识应该用二分查找法，我们最先初始化left和right为0和数组长度len-1，然后取中间值mid，比较citations[mid]和len-mid做比较，如果前者大，则right移到mid之前，反之right移到mid之后，终止条件是left>right，最后返回len-left即可

    int hIndex(vector<int>& citations) {
        int len = citations.size(), left = 0, right = len - 1;
        while (left <= right) {
            int mid = 0.5 * (left + right);
            if (citations[mid] == len - mid) return mid + 1;
            else if (citations[mid] > len - mid) right = mid - 1;
            else left = mid + 1;
        }
        return len - left;
    }

def hIndex(self, citations): N = len(citations) cnts = [0] * (N + 1) for c in citations: cnts[[c, N][c > N]] += 1 sums = 0 for h in range(N, 0, -1): if sums + cnts[h] >= h: return h sums += cnts[h] return 0
http://segmentfault.com/a/1190000003794831

    public int hIndex(int[] citations) {
        int n = citations.length;
        if(n == 0) return 0;
        int min = 0, max = citations.length - 1;
        while(min <= max){
            int mid = (min + max) / 2;
            // 如果该点是有效的H指数，则最大H指数一定在右边
            if(citations[mid] < n - mid){
                min = mid + 1;
            // 否则最大H指数在左边
            } else {
                max = mid - 1;
            }
        }
        // n - min是min点的H指数
        return n - min;
    }

https://github.com/kamyu104/LeetCode/blob/master/C++/h-index-ii.cpp

	int hIndex(vector<int>& citations) {
	const int n = citations.size();
	int left = 0;
	int right = n - 1;
	while (left <= right) {
	const auto mid = left + (right - left) / 2;
	if (citations[mid] >= n - mid) {
	right = mid - 1;
	} else {
	left = mid + 1;
	}
	}
	return n - left;
	}

Read full article from [LeetCode]H-Index II | 书影博客