[leetCode] Top Interview 150: Majority Element

リンク

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

概要

• 整数配列numsが与えられる
• numsには必ずnums.length / 2以上を占めるある値が入っている
• その値を返す

解法

ムーアの多数決アルゴリズムというものを利用する。

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = 0;
        int count = 0;

        for(int n: nums) {
            if(count == 0) candidate = n;
            if(candidate == n) {
                count++;
            } else {
                count--;
            }
        }

        return candidate;
    }
}

このへんを参考にしました。

簡単にシステムを説明すると、

• 候補者(ここではcandidate)と、カウンタ(ここではcount)を保存する変数を用意する
• 配列を走査し、以下の条件に従って変数を操作する
  • カウンタが0: 候補者をリセット（今指してる値にする）
  • 候補者が現れる: カウンタに+1
  • 候補者以外が現れる: カウンタに-1
• 最終的に残った候補者 = 過半数を獲得した者

というアルゴリズム。
あくまで必ず過半数を獲得することが保証されている状態で有効になる点に注意。
実際に使う場合はこのアルゴリズムの後に検証処理が必要になりそう。

メモ2: ほかの解き方

Solutionを見ててよく見かけたのが、以下のコード。

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        return nums[n/2];
    }
}

ソートして中央値を取得すると、それが必ず過半数を占める値になる、というもの。
ただ、個人的には[1,1,1,2,2,3]のような場合に誤って2を指してしまうのでは？と思い、使わなかった。（このへん間違ってたらすみません）

あとがき

アルゴリズムに対して「これはツールなんだ、内部構造を考える必要はないんだ」と思いながら学んでいます。知的好奇心の抑え込み。