tsanmmmm2000's Tech Blog

Question

Given an array of size n, find the majority element. The majority element is the element that appears more than [ n/2 ] times.

You may assume that the array is non-empty and the majority element always exist in the array.

Thinking

此題我們最先想到的是利用Dictionary或HashMap來記錄每個元素出現的次數

public class Solution {
    public int MajorityElement(int[] nums) {
        var map = new Dictionary<int, int>();
        var result = nums[0];
        for (var i = 0; i < nums.Length; i++)
        {
            var num = nums[i];
            if (map.ContainsKey(num))
            {
                map[num] += 1;
                if (map[num] > nums.Length / 2)
                {
                    result = num;
                    break;
                }
            }
            else
            {
                map.Add(num, 1);
            }
        }
        return result;
    }
}

不過在討論區中，我們發現一個更為強大且簡潔的解法，那就是利用Boyer–Moore Majority Vote Algorithm，而題目有提到majority element一定存在，因此最後遺留下來的便會是答案；反之若majority element可能不存在，那我們最後就得再掃一遍原來的陣列以資證明

My C# Solution

public class Solution {
    public int MajorityElement(int[] nums) {
        var count = 1;
        var result = nums[0];
        for (var i = 1; i < nums.Length; i++)
        {
            var num = nums[i];
            if (count == 0)
            {
                result = num;
                count++;
            }
            else if (result == num)
            {
                count++;
            }
            else
            {
                count--;
            }
        }
        return result;
    }
}

Reference：Boyer–Moore majority vote algorithm - Wikipedia