PythonでリストBの少なくともk個の要素より厳密に小さいリストAの要素数を求める方法

数値のリストAとB、および整数kが与えられたとき、「Bの少なくともk個の要素よりも厳密に小さい」Aの要素の個数を求める問題を考えてみましょう。

例えば、入力が A = [6, -2, 100, 11]、B = [33, 6, 30, 8, 14]、k = 3 の場合、出力は 3 になります。これは、-2、6、11 の3つの要素が、それぞれBの3つ以上の要素よりも厳密に小さいためです。

解法のアプローチ

この問題は、以下の手順で効率的に解くことができます。

• kが0の場合は、条件が常に満たされるため、Aの要素数をそのまま返します。
• Bを降順にソートします。これにより、B[k-1]は「Bの中でk番目に大きい要素」となります。
• カウンタctを0で初期化します。
• Aの各要素iについて、i < B[k-1] が成り立てば、その要素はBの上位k個すべてより小さいことになるため、ctを1増やします。
• 最終的なctを結果として返します。

この方法のポイントは、Bを降順にソートしておくことで、Aの各要素が条件を満たすかどうかを1回の比較だけで判定できる点です。AとBのすべての組み合わせを比較する方法（計算量 O(n×m)）と比べ、この手法では O(n log n + m) で処理でき、データ量が多い場合でも高速に動作します。

実装例

class Solution:
    def solve(self, A, B, k):
        if k == 0:
            return len(A)
        B.sort(reverse=True)
        ct = 0
        for i in A:
            if i < B[k - 1]:
                ct += 1
        return ct

ob = Solution()
A = [6, -2, 100, 11]
B = [33, 6, 30, 8, 14]
k = 3
print(ob.solve(A, B, k))

入力

[6, -2, 100, 11], [33, 6, 30, 8, 14], 3

出力

3