[leetCode] Top Interview 150: H-Index

リンク

https://leetcode.com/problems/h-index/?envType=study-plan-v2&envId=top-interview-150

概要

• 論文の引用回数を示す配列citationsが与えられる
  • たとえばi_nは、「n番目に執筆した論文がi_n回引用された」ことを示す
• このデータをもとに、H-indexを求める
  • H-index: 研究者が出版した論文のなかで、被引用数がh以上であるものがh以上あることを満たす最大の数値
  • たとえば H-index=3 のとき、「3回以上引用された論文が3つ以上ある」ということ

解法

普通に考える

まずは自分で考えた解法。

前提として、H-indexの最大値は配列のサイズと同じになる。
そのため、H-indexの範囲は 0~n (nは配列の大きさ）となる。

H-indexの範囲に対して数え上げを実行し、条件を満たすものがあれば返す。
なければ0を返す。

class Solution {
    public int hIndex(int[] citations) {
        int ans = 0;
        for(int i=citations.length; i>=0; i--) {
            int count = 0;
            for(int j=0; j<citations.length; j++) {
                if(citations[j] >= i) {
                    count++;
                }
            }

            if(count >= i) {
                ans = i;
                break;
            }
        }

        return ans;
    }
}

これでも一応通ったけど、計算量は$O(N^2)$なのでめっちゃ遅い。

カウントソート

いい感じの解法を見つけたので紹介。

カウント用に配列を用意し、citationsの要素をカウントしていく。
その後、まとめて数え上げをし、条件を満たしたら返す、といったアルゴリズム。

時間計算量は$O(N)$, 空間計算量は$O(N)$。

class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int[] counts = new int[n+1];

        for(int c : citations) {
            if(c >= n) {
                counts[n]++;
            } else {
                counts[c]++;
            }
        }

        int count = 0;
        for(int i=n; i>=0; i--) {
            count += counts[i];
            if(count >= i) {
                return i;
            }
        }

        return 0;
    }
}

上の考え方をそのままに、処理速度を改善した形になる。