【leetcode】275. H指数2

本题的代码实测正确，但思路分析部分个人感觉还有点含糊，请谨慎查看思路分析部分。

题目内容

275.H指数2

思路分析

本题是274.H指数的扩展，两道题的区别是本题直接给定了排好序的数组，不用再将给定的数组进行排序操作。根据本题的提示，本题的考察重点为实现一个*O(log N)*时间复杂度的算法。

给定升序引用次数列表后，问题便简化为：在大小为n 的升序引用次数列表中，找到满足citations[i] >= n - i 的第一个citations。因此本题可以使用二分查找。我在解274题时，将列表排好序后用了线性查找，时间复杂度为O(N)，其实现在回想起来，稍微懂点算法的人肯定立即就想到用二分查找来降低时间复杂度至O(log N)了...

本题更加类似于C++的std库函数lower_bound（找到数组指定范围内第一个大于等于指定值的元素）。根据citations[i] 与n - i 是否相等，可分为两种不同的情况（如下的表1和表2）。

列出如下的表格可以辅助我理解要找到怎么样的目标以及二分查找的方向。（因为至今我仍然觉得这个H指数的概念很绕，但是同样觉得很绕的小伙伴也不用自闭，因为大家都是这么认为的，哈哈）

表一：citations[i] = n - i

如表一所示，我们要找到的目标是pivot = 4的那列。

表二：citations[i] > n - i

如表二所示，我们要找到的目标是pivot = 1的那列。

因此以表一为例，设二分查找的各参数为left,pivot,right，得出以下查找算法：

1. 当citations[pivot] = n - pivot时，找到了H指数，返回n - pivot

2. 若citations[pivot] < n - pivot，证明正确的范围应该在pivot的右边，故令left = pivot + 1

3. 若citations[pivot] > n - pivot，证明正确的范围应该在pivot的左边，故令right = pivot - 1

4. 当遍历完毕，即left = right时，证明是属于表二的情况，即不存在citations[pivot] = n - pivot的情况。此时最终二分查找的left会停留在第一个满足citations[pivot] > n - pivot的解上，right会停留在第一个满足citations[pivot] < n - pivot的解上。因此需要返回n - left = 4 - 1 = 3。（这种情况还是感觉略含糊，这种解释来自于leetcode英文社区的讨论区的@XiaoweiLu的评论，找了很久这个的解释，只找到这个还不错）

       left
        v  
     1, 4, 5, 5
     ^
   right
   

代码

#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    // 时间复杂度：O(log n)，空间复杂度：O(1)
    int hIndex(vector<int>& citations) {

        int n = citations.size();
        int left{ 0 }, right{ n - 1 }, pivot{ 0 };

        // Tips: 下面这句话错误，因为C++11列表初始化时如果有信息丢失的风险，则会报错
        // int left{ 0 }, n{ citations.size() }, right{ n - 1 }, pivot{ 0 };


        while (left <= right) {
            pivot = (left + right) / 2;
            if (citations[pivot] < n - pivot) {
                left = pivot + 1;
            } else if (citations[pivot] > n - pivot) {
                right = pivot - 1;
            } else {
                return n - pivot;
            }
        }

        return n - left;
    }
};


int main() {
    Solution s;
    vector<int> input{ 1,1 };

    int output{ 0 };
    output = s.hIndex(input);

    return output;
}

收获

• 加深了对之前的题目274.H指数的理解。

• 加深了对二分查找的理解

• 培养了线性查找->二分查找的优化思维

• 知道了C++有lower_bound这么个函数

• 知道了C++列表初始化时会检查是否发生了类型的收窄

• 发现leetcode英文社区有非常多的相关讨论和资料，如本题的中文社区资料感觉比较匮乏，不能解答我的疑惑，以后可以多参考英文社区的资料。（ps.发现英文社区有好多活跃的中国人-.-）