274. H-Index

發表於 | 分類於

problem

solution

option 1

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n= citations.size();
        sort(citations.begin(), citations.end(), greater<>()) ;
        for(int i =0;i<n;++i){
            if(citations[i] <= i) return i;
            
        }
        return n;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int hIndex(vector<int>& citations) {
        int ret= 0 ,n=citations.size();
        sort(citations.rbegin(), citations.rend());
        
        
        for(int i=0;i<n;++i){
            if(citations[i]>i) ret++;
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n= citations.size();
        sort(citations.begin(), citations.end(), greater<>()) ;
        int l = 0, r= n-1;
        while(l<=r){
            
            int mid = l + (r-l)/2;
            if(citations[mid] > mid ) l = mid+1;
            else r = mid - 1;
        }
        return l;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int hIndex(vector<int>& citations) {
        int ret= 0 ,n=citations.size();
        sort(citations.rbegin(), citations.rend());
        //  0   1   2   3   4
        //  6   5   3   1   0
        
        //  0   1   2
        //  3   1   1
        int l = 0, r = n;
        while(l<r){
            int mid = l +(r-l)/2;
            if(citations[mid]>mid) l = mid+1;
            else r= mid;
            
        }
        return l;
    }
};

analysis

  • time complexity O(nlogn)
  • space complexity O(1)