c++ - h指数计算以获取建议

研究算法难题。发布问题陈述和代码。我的问题是，对于最后一行，return citations [right]是否总是与return len-(right + 1)相同的结果？我尝试了几个测试用例，似乎两者具有相同的值(value)。想征询意见是什么时候反样本有所不同？谢谢。

给定研究人员的一系列引文(每个引文是一个非负整数)，编写一个函数来计算研究人员的h指数。

根据Wikipedia上h-index的定义:“如果科学家的N篇论文中的h篇每篇至少被h引用，而其他N － h篇每篇不超过h篇引用，则科学家对h进行索引。”

例如，给定的引文= [3，0，6，1，5]，这意味着研究人员总共有5篇论文，每篇论文分别收到了3，0，6，1，5篇引文。由于研究人员拥有3篇论文，每篇被至少引用3次，其余两篇论文每篇被引用不超过3次，因此他的h指数为3。

如果citations数组按升序排序怎么办？您可以优化算法吗？

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

提前致谢，
林

最佳答案

首先，无论如何，您的实现只能在上对排序的输入起作用，对吗？

现在想象一下输入:

vector<int> v{1,2,5,6,9};

此输入将返回不同的值，用于:

return len - (right+1);    // returns 3 (correct answer)
return citations[right];   // returns 2 (wrong answer)

但是，您可以执行以下操作:

return len-left;

这样做是因为right+1在此行上始终等于left(鉴于您的代码)。

考虑while循环的退出条件以及以下事实:在每个迭代上left和right之间的差异最多只能由1改变。

总体而言，最好的解决方案是先对输入的内容进行排序，然后再进行二进制搜索，从而使O(N log N)的时间复杂度加在一起。

没有比这更好的了。

旁注:我会避免使用>>1之类的代码，而不是简单地除以2，因为这会损害可读性，没有任何好处。我假设您使用的是合理的编译器(具有优化功能)。

关于c++ - h指数计算以获取建议，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/33728252/