-
https://leetcode.cn/problems/h-index/description/?envType=study-plan-v2&envId=top-interview-150
注：題目有點難理解，多讀幾遍
可以這樣考慮，建立另一個臨時數(shù)組temp，當(dāng)?shù)?em>i篇文章被引用citiations[i]次時，令j<=citiations[i]的temp[j]均加一，也就是現(xiàn)在對于任意j至少有temp[j]篇論文引用次數(shù)大于等于j。因為h是最大值，那么遍歷temp最后一個滿足temp[j]>=j的j就是所求。
當(dāng)然，以上的時間復(fù)雜度和空間復(fù)雜度都比較大，另一種好的方法是先排序后遍歷。
先將數(shù)組citiations進(jìn)行排序，如何從大的一端向小的一端遍歷，那么令h一開始為0，每當(dāng)遍歷到一個citiations[i]時，就說明多了一個滿足條件的論文，h也就可以加一，直到"h大于citiations[i]"時，也就意味著不在存在滿足條件的論文了，遍歷也就結(jié)束了。
實現(xiàn)代碼：
class Solution {
public:
int hIndex(vector<int>& citations) {
int temp[5001]={0};
int h=0;
for(int i=0;i<citations.size();i++){
for(int j=1;j<=citations[i];j++){
temp[j]++;
}
}
for(int i=1;i<5000;i++){
if(temp[i]>=i){
h=i;
}
}
return h;
}
};
class Solution {
public:
int hIndex(vector<int>& citations) {
sort(citations.begin(), citations.end());
int h = 0, i = citations.size() - 1;
while (i >= 0 && citations[i] > h) {
h++;
i--;
}
return h;
}
};
本文由博客一文多發(fā)平臺 OpenWrite 發(fā)布！文章來源地址http://www.zghlxwxcb.cn/news/detail-841289.html
文章來源：http://www.zghlxwxcb.cn/news/detail-841289.html
到了這里，關(guān)于LeetCode刷題記錄——day1的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
