プログラマー-H-Index

プログラマー-H-Index
Kakaoの問題を解くとき頭が痛くて休憩中に問題を解いて、解いてから他の人のコードを見て、斬新な解があることに気づいて、びっくりしました.
まずソートカテゴリの降順にソートした後、iの1番目の要素のサイズがi+1未満の場合、iを返します.
例えば、[6,5,3,1,0]
i=0から1<=6になり、次へ移動します.
i=1から2<=5まで続き、
i=2から3<=3まで続き、
i=3から4>1、3を返してくれればいいのに.
すなわち,i+1はこれまでの論文数を意味する.
降順で並べられているので,これまでの論文数が引用文量より少ない場合,H−Indexに設定すれば,引用文量がより小さくなるまで数えることができる.
引用文はこれまで、論文の数より少ない場合は、すぐに正解に返信することができます.(最初のコード)
これが思いつかない場合は、最も多く参照されている[k]値から0にループして参照することもできます.(第2セグメントコード)
私は最初に1つ目の解を使ってみたが、不等号の間違いを犯して、まず2つ目を解いて、それから1つ目を解いて、他の人のコードを見て、誰かがバイナリで問題を検索していることに気づいたので、私はついて行った.
mid値が現在のh-indexであり、参照中にmid値を超える要素数がmidより大きい場合、leftをh-indexに設定できるため、leftをmidに設定します.
mid値以上の要素の個数がmidより小さい場合、現在のh-index(mid)値が大きすぎてrightをmidに設定し、バイナリ検索を行えばよい.
1番目のコードについては,ソートオーバーヘッドによりO(NlogN),2番目はO(NlogN)かもしれないが,非常に遅いコードであり,O(N^2)に近い.
3つ目はバイナリ解なのでO(N)に近いO(Nlogn)である.(バイナリ探索の発生回数を定数とするとO(N)とすることができる.)
実際、結果もバイナリ検索が最も速く、1つずつ比較するコードが最も遅い.

int solution(vector<int> citations) {
    int answer = 0;
    sort(citations.begin(), citations.end(), greater<>());
    int size = citations.size();
    int max_element = citations[0];
    
    for(int i=0;i<size;i++) 
        if(i + 1 > citations[i]) 
            return i;
        
    return size;
}

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> citations) {
    int answer = 0;
    int size = citations.size();
    sort(citations.begin(), citations.end(), greater<>());
    int max_value = citations[0];
    for(int i=max_value;i>0;i--) {
        int cnt = 0;
        for(int j=0;j<size;j++) {
            if(citations[j] < i)
                break;
            cnt++;
        }
        if(cnt >= i) {
            answer = i;
            break;
        }
    }
    return answer;
}

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool binary(const vector<int> &citations, const int &size, int mid)
{
    int cnt = 0;
    for(int i=0;i<size;i++) 
        if(citations[i] >= mid)
            cnt++;
    
    return cnt >= mid;
}

int solution(vector<int> citations) {
    int answer = 0;
    int size = citations.size();
    
    int left = 0;
    int right = 1 << 14;
    
    while(left + 1 < right) {
        int mid = (left + right) / 2;
        
        if(binary(citations, size, mid)) {
            answer = mid;
            left = mid;
        } else 
            right = mid;
    }
    return answer;
}