H-index I && II

這是評論一個人的論文水準, 假設他總共發五篇

[3,0,6,1,5]

他有三篇以上的論文獲得三個以上的citation, 他的h-index就是3

我們先排序, 然後從後面依序看回來,

[0,1,3,5,6]

先看6, 這時的h-index是1

5 h-index:2

3 h-index:3

1 因為1的citation太少, 所以就不會再增加h-index直了

class Solution {
public:
    int hIndex(vector<int>& citations) {
        sort(citations.begin(), citations.end());
        int res = 0;
        int j = 1;
        for(int i = citations.size() - 1; i>=0;i--,j++){
            if(citations[i] >=j){
                res = max(res, j);
            }
        }
        return res;
    }
};

但這要排序 時間複雜度是O(nlogn)

另外一個做法只要O(n)

首先, 我們給出n+1個桶子, index分別是1~n

接著, 假設大於n 我們就放到第n個, 其餘就按各自的index放

最後, 我們從最後一個桶子看, 假設第n個桶子(最優質的論文), 引用次數大於了n, 我們就往前看, 反正保底已經是這幾張優質論文會是我的h-index, 若找到剛好, 若count數剛好等於index, 直接輸出, 因為接下來的index不可能高過count了(index只會越來越小)

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int res;
        int n = citations.size();
        vector<int> buckets( n+1, 0);
        for(auto &b: citations){
            if(b>n){
                buckets[n]++;
            }else{
                buckets[b]++;
            }
        }
        int count = 0;
        for(int i = n; i >= 0; i--) {
            count += buckets[i];
            if(count >= i) {
                return i;
            }
         }
         return 0;
    }
};

因為他說O(logn)了, 基本上就是二分搜尋

不過要注意index的使用方式,

假設當長度大於當前cts的值, 表明說, 你設這個值當index恐怕太低, 可以往上增加試看看

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