已婷婷狠狠18禁久久YY,嫩草久久99www亚洲红桃,婷婷精品视频在线,久久综合色鬼,日韩在线视频一区二区三区,国产AV天堂,国产精品96久久久久久,丝袜操逼网

算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識(shí)和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個(gè)公眾號(hào)后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問題叫做 H 指數(shù) II，我們先來看題面：

https://leetcode-cn.com/problems/h-index-ii/

Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper and citations is sorted in an ascending order, return compute the researcher's h-index.

According to the definition of h-index on Wikipedia: A scientist has an index h if h of their n papers have at least h citations each, and the other n ? h papers have no more than h citations each.

If there are several possible values for h, the maximum one is taken as the h-index.

You must write an algorithm that runs in logarithmic time.

給定一位研究者論文被引用次數(shù)的數(shù)組（被引用次數(shù)是非負(fù)整數(shù)），數(shù)組已經(jīng)按照升序排列。編寫一個(gè)方法，計(jì)算出研究者的 h 指數(shù)。

h 指數(shù)的定義: “h 代表“高引用次數(shù)”（high citations），一名科研人員的 h 指數(shù)是指他（她）的（N 篇論文中）總共有 h 篇論文分別被引用了至少 h 次。（其余的 N - h 篇論文每篇被引用次數(shù)不多于 h 次。）"

示例

輸入: citations = [0,1,3,5,6]
輸出: 3 
解釋: 給定數(shù)組表示研究者總共有 5 篇論文，每篇論文相應(yīng)的被引用了 0, 1, 3, 5, 6 次。
  由于研究者有 3 篇論文每篇至少被引用了 3 次，其余兩篇論文每篇被引用不多于 3 次，所以她的 h 指數(shù)是 3。

解題

https://blog.csdn.net/qq_41855420/article/details/88210221

此題給的條件是遞增的數(shù)組序列，所以我們需要充分利用。

方法一：從后往前遍歷數(shù)組，如果出現(xiàn)引用大于等于hRes次的論文數(shù)量大于、等于hRes時(shí)，hRes就是結(jié)果。（時(shí)間復(fù)雜度O(n)，額外的空間復(fù)雜度O(1)）

class Solution {
public:
  int hIndex(vector<int>& citations) {
    int citationsSize = citations.size();
    int cnt = 0, hRes = citationsSize;//cnt表示引用次數(shù)大于、等于hRes論文數(shù)，hRes代表的是當(dāng)前的標(biāo)準(zhǔn)，初始化為最大值
        //注意循環(huán)條件index >= 0表示不出界，cnt < hRes表示引用次數(shù)大于等于hRes的論文數(shù)cnt小于hRes
    for (int index = citationsSize - 1; cnt < hRes && index >= 0; ) {
      if (hRes <= citations[index]) {//citations[index]表示的當(dāng)前論文引用的次數(shù)超過了標(biāo)準(zhǔn)
        cnt += 1;
        index -= 1;
      }
      else {//否則需要降低標(biāo)準(zhǔn)
        hRes -= 1;
      }
    }
    return hRes;
  }
};

方法二：提到log(n)的時(shí)間復(fù)雜度，那么與二分法一般都分不開。

class Solution {
public:
  int hIndex(vector<int>& citations) {
    int citationsSize = citations.size();
        if (citationsSize == 0){
            return 0;
        }
    //二分法的左、中、右指針
    int left = 0, mid, right = citationsSize - 1;
    while (left < right) {
      mid = (left + right) / 2;
      //因?yàn)閿?shù)組遞增，所以mid下標(biāo)之后的論文引用次數(shù)必定 >= citations[mid]
      //citationsSize - mid代表是從下標(biāo)mid到末端[mid, citationsSize - 1]含有的論文數(shù)
      //citations[mid] >= citationsSize - mid進(jìn)行判斷mid是否符合標(biāo)準(zhǔn)
      //因?yàn)樾枰业紿的最大值，所以citationsSize - mid需要盡可能的大
      if (citations[mid] >= citationsSize - mid) {
        right = mid;
      }
      else {
        left = mid + 1;
      }
    }
    //防止所有的所有的論文引用都是0的情況，如果不加特殊處理，將會(huì)返回1
    if (citations[right] < citationsSize - right) {
      return 0;
    }
    return citationsSize - right;
  }
};