程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> leetcode筆記:H-Index II

leetcode筆記:H-Index II

編輯:C++入門知識

leetcode筆記:H-Index II


一. 題目描述

Follow up for H-Index: What if the citations array is sorted in ascending order? Could you optimize your algorithm?

二. 題目分析

該題與H-Index一題的要求基本一致,只是多提供了一個條件,即傳入的數組本身已經是升序排列的,因此實際上操作會方便許多,也無需再使用輔助數組。該題仍然可以使用H-Index方法從後往前遍歷數組,即可計算出h指數,算法復雜度為O(n),但更快的方法是使用二分查找,復雜度降為O(logn)

三. 示例代碼

// 簡單的從後往前遍歷數組,較為耗時
class Solution {
public:
    int hIndex(vector& citations) {
        if (citations.size() == 0) return 0;
        int result = 0;
        for (int i = citations.size() - 1; i >= 0; --i)
        {
            if (result >= citations[i])
                return result;
            ++result;
        }
        return citations.size();
    }
};
// 二分查找,效率更快
class Solution {
public:
    int hIndex(vector& citations) {
        int size = citations.size();
        if (size == 0)
            return 0;
        int left = 0, right = size - 1;
        while (left < right){
            int mid = left + (right - left) / 2;
            if (size - mid > citations[mid])
                left = mid + 1;
            else
                right = mid;
        }
        return (size - right) < citations[right] ? (size - right) : citations[right];
    }
};

四. 小結

題目的提示略顯多余。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved