Pythonで他の要素の少なくとも2倍の最大数を判定する方法

整数型の配列 nums が与えられます。この配列には常にちょうど1つの最大要素が存在すると仮定します。ここでの課題は、配列内の最大要素が、それ以外のすべての要素の少なくとも2倍の値を持っているかどうかを判定することです。条件を満たす場合は最大要素のインデックスを返し、満たさない場合は -1 を返します。

問題の例

例えば、入力が [3, 6, 1, 0] の場合を考えてみましょう。このとき出力は 1 となります。6が配列内の最大値であり、他のすべての要素（3、1、0）に対して6は2倍以上の大きさだからです。6のインデックスは1であるため、結果として1が返されます。

解法のアプローチ

この問題を解くために、以下の手順に従います。

• ステップ1: 変数 maximum に配列 nums の最大値を代入します。
• ステップ2: インデックス i を0から配列のサイズまでループさせます。
  • nums[i] が maximum と等しい場合は、その位置を maxindex として記録します。
  • nums[i] が maximum と等しくなく、かつ maximum < 2*(nums[i]) を満たす場合は、-1 を即座に返します。
• ステップ3: ループが完了したら、記録しておいた maxindex を返します。

Pythonによる実装例

理解を深めるために、以下の実装コードを見てみましょう。

class Solution:
    def dominantIndex(self, nums):
        maximum = max(nums)
        for i in range(len(nums)):
            if nums[i] == maximum:
                maxindex = i
            if nums[i] != maximum and maximum < 2*(nums[i]):
                return -1
        return maxindex
ob = Solution()
print(ob.dominantIndex([3, 6, 1, 0]))

入力

[3, 6, 1, 0]

出力

1

計算量の分析

このアルゴリズムの時間計算量は O(n) です。まず max() 関数で最大値を求める際に配列を一度走査し、その後もう一度走査して条件を確認するため、全体として要素数に比例した線形時間で処理が完了します。また、使用する変数は定数個のみなので、空間計算量も O(1) と非常に効率的です。