计算 h-index （2）

之前写了一篇关于计算影响因数h-index的文章，上面提出了一种 O(n* log n) 复杂度的算法，今天的文章提出一种O(n)复杂度的方法。原始文章见这里。

问题，存在一个列表，该表内有n个数大于等于n，求n的最大值。

例如     【3,10,5,1,7】答案为3

        【1,100,1000,20】答案为3

 

最近做了一些双向队列的算法，对列表处理有了新的感悟。通过双向列表可以实现线性复杂度，只不过逻辑比较复杂。基本思想为：用一个双向队列存储已经读入的值，队尾为较大值，队首放着较小值。每当队列长度大于h_index时，依次从队首删除元素。此外还删除所有小于h_index值的元素。

 

基本步骤如下：

1）初始化一个双向列表q，向表内放置一个初始元素0。用于存放结果的h_index变量初始化为0。

2）依次读入数据列表值i,并进行如下循环：若i>0且h_index==0,则将h_index赋值为1 (存在1篇大于1的文章).否则进行如下判断:

(q.size()>=h_index) &&(q.front()>h_index)&&((i>q.back())||(i>h_index)))

若为真则++h_index

3）从队首弹出元素，直到空或者队首值大于h_index

4）若i大于队列尾部，将i推入队尾，否则推入队首

5）若当前队中元素个数大于h_index，从队首依次弹出。

6）重复步骤2~5

 

例如数据【3,4,3,4,5】

1. 首先将3读入，h_index=1，q={3}

2. 将4读入，由于当前队列大小与h_index相等且4>h_index，h_index=2，q={3,4}

3. 将3读入，根据判断条件，h_index=3，q={3,3,4}，但经过元素删除操作，q={3,4}

4. 将4读入，根据条件，h_index=3不变，但需要更新队列，q{3,3,4}-> q{4} -> q{4,4}

5. 将5读入，h_index=4，队列更新为q{5},并返回h_index=4

 

这里我们能看到q的作用，用于记录到下一个h_index还差多少数据，比如最后的q{5}和h_index表明，当前最大值为5，h_index为4，至少还要有4个大于5的元素才能使队列大小与h_index相等，之后 h_index才能变成5。

代码如下：

int hval(const vector<int> H) {
	deque<int>q;
	q.push_back(0);
	int hval = 0;
	for (auto i : H) {

		if (hval == 0 && i > 0)hval = 1;
		else if(  (q.size()>=hval) && (q.front()>hval)&&((i>q.back())||(i>hval)))
			++hval; 

		while (!q.empty() && q.front() <= hval)
			q.pop_front();
		if (q.empty() || i > q.back())
			q.push_back(i);
		else q.push_front(i);
		while (q.size() > hval)
			q.pop_front();
	}
	return hval;
}

代码中每个元素最多只入队和出队一次，因此复杂度为O(n)