Pythonで配列内のK番目に大きい要素を求める方法

問題の概要

ソートされていない配列が与えられたとき、その中からk番目に大きい要素を見つける必要があります。例えば、配列が [3,2,1,5,6,4] で k = 2 の場合、2番目に大きい要素は「5」なので、結果は5となります。

解決のアプローチ

この問題は、以下の手順で解決できます。

• まず、配列の要素を昇順にソートします。
• kが1の場合は、最大値（配列の末尾の要素）をそのまま返します。
• それ以外の場合は、array[n - k] を返します。ここで n は配列のサイズです。

ソート後の配列は昇順に並んでいるため、末尾から数えてk番目の位置、つまりインデックス n-k の要素が求める「k番目に大きい要素」と一致するという仕組みです。

実装例

以下にPythonでの実装例を示します。

class Solution(object):
    def findKthLargest(self, nums, k):
        nums.sort()
        if k == 1:
            return nums[-1]
        temp = 1
        return nums[len(nums)-k]

ob1 = Solution()
print(ob1.findKthLargest([56,14,7,98,32,12,11,50,45,78,7,5,69], 5))

入力

[56,14,7,98,32,12,11,50,45,78,7,5,69]
5

出力

50

コードの解説

このコードでは、まず nums.sort() によって配列を昇順にソートしています。kが1の場合は配列の最後の要素（最大値）を返し、それ以外の場合は len(nums)-k 番目のインデックスにある要素を返します。

上記の例では、配列のサイズが13で k = 5 であるため、インデックス 13 - 5 = 8 の位置にある要素「50」が出力として得られます。

計算量について

このアプローチの時間計算量は O(n log n) です。Pythonの sort() メソッドがTimsortアルゴリズムを採用しているためです。より効率的な手法を求める場合は、heapq モジュールを利用したヒープによる O(n log k) のアプローチや、クイックセレクトによる平均 O(n) のアプローチも検討できます。