Swiftで数値で構成された配列の中から過半数を超える値を抽出するアルゴリズム

概要

169. Majority Elementを解いていると面白い解き方があったのでメモを残しておきます。

こちらは与えられた配列中の過半数を超える値を返却するような関数を書く、という問題です。

以下が169. Majority Elementで与えられる入力例と出力例です。

Majority Element

Example 1:
Input: nums = [3,2,3]
Output: 3

Example 2:
Input: nums = [2,2,1,1,1,2,2]
Output: 2

Example 1では3が過半数を超える値であるため3を、Example 2では2が過半数を超える値であるため、2を返しています。

また、問題文中に多数決要素は常に配列中に存在すると仮定してもよいと記載があるので、過半数を超える値が存在しない状況は考えなくても良いことになります。

なお、ここでは以下のような制約が存在します。

n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109

詳細

自分の解法

Majority Element

class Solution {
    func majorityElement(_ nums: [Int]) -> Int {
        var counts = [Int:Int]()

        for n in nums{
            counts[n,default:0] += 1
        }
        
        var maxElement = 0
        var maxCount = 0

        for (element,count) in counts{
            if count > maxCount{
                maxCount = count
                maxElement = element
            }
        }

        return maxElement
    }
}

配列内に存在する値とその値が出現する回数をDictionaryで保存しておき、そのDictionary内で最もValueの値が大きい値を返す、というものです。
計算量,空間計算量共にO(N)です。

これ自体はよくある解法で、パッと思いつきやすい内容だと思います。

これで終わりかと思っていましたが、問題文の最後の方に書いてある文字に気が付きました。

Follow-up: Could you solve the problem in linear time and in O(1) space?
(この問題を線形時間と空間計算量をO(1)で解くことができますか？)

こう書いてあるということは、この問題には空間計算量をO(1)に落とせる解法があるのです。
それが次の解法です。

Boyer-Moore Voting Algorithm

Boyer-Moore Voting Algorithmは、与えられた配列内で出現回数が過半数を超える要素（majority element）を効率的に見つけるためのアルゴリズムで、配列内の値を線形時間、そして追加のメモリ空間を使用することなく配列内の過半数を超える要素を見つけることができます。

ここで注意しなければならないのは、与えられた配列内に過半数の要素が存在することが前提条件となっていることです。

今回に関してはその前提が満たされているため、このアルゴリズムが適用可能となっています。

Majority Element

class Solution {
    func majorityElement(_ nums: [Int]) -> Int {
        var majority = 0
        var count = 0
        for n in nums{
            if count == 0{
                majority = n
                count += 1
            }else if n == majority {
                count += 1
            }else{
                count -= 1
            }
        }
        return majority
    }
}

単純なcountの増減だけで過半数を判定できることに気付けなかったのが少し悔しくなりました。

こちらの解法の計算量はO(N)で、空間計算量はO(1)です。
特定の変数しか追加しないため、Dictionaryを使用する時よりもメモリの使用量が少なくなります。