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:

  1. Expected runtime complexity is in O(log n) and the input is sorted.

LeetCode H-Index的延伸,如果citations是按升序排列的,怎样把算法优化到O(logn)。看到O(logn),马上想到二分查找。

首先左右边界是0和n-1,判断中点的citations[m]和n-m,如果正好相等,则说明正好有n-m篇大于等于n-m引用的文章,所以H-index为n-m。如果citations[m]>n-m,说明引用很大,h-index还能往上涨,所以中心点需要左移,即r=m-1。反之则中心点右移l=m+1。

代码如下:

class Solution {
public:
	int hIndex(vector<int>& citations) {
		int l = 0, n = citations.size(), r = n - 1;
		while (l <= r) {
			int m = l + (r - l) / 2;
			if (n - m == citations[m])return n - m;
			else if (citations[m] > n - m)r = m - 1;
			else l = m + 1;
		}
		return n - l;
	}
};

本代码提交AC,用时9MS。

我一开始的代码是,如果citations[m]<n-m,中心点确实右移了,即l=m+1。但是当citations[m]>n-m时,我没想到用r=m-1来左移中心点,误以为r一直都是n-1是固定的,所以这个时候使用了一个while循环来线性查找正确的m,理论上性能要比上面的纯二分差。

代码如下:

class Solution {
public:
	int hIndex(vector<int>& citations) {
		int l = 0, r = citations.size() - 1, n = citations.size();
		if (n == 0)return 0;
		if (citations[0] >= n)return n;
		while (l < r) {
			int m = l + (r - l) / 2;
			if (n - m>citations[m])l = m + 1;
			else {
				while (m > 0 && n - m <= citations[m])--m;
				return n - m - 1;
			}
		}
		if (citations[r] >= 1)return 1;
		else return 0;
	}
};

本代码提交AC,用时也是9MS。

Leave a Reply

Your email address will not be published. Required fields are marked *