LeetCode – Majority Element (Easy)

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1:

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

Example 2:

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

Constraints:

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

Follow-up: Could you solve the problem in linear time and in O(1) space?

我的第一版本:

public class Solution {
    public int MajorityElement(int[] nums) {
        if (nums.Length == 1)
            return nums[0];
            
        var max = nums.Length / 2;
        var result = 0;
        Dictionary<int, int> counter = new Dictionary<int, int>();
        foreach(var n in nums)
        {
            if (counter.ContainsKey(n))
            {
                counter[n]++;
                if (counter[n] > max)
                {
                    max = counter[n];
                    result = n;
                }
                    
            }
            else
            {
                counter.Add(n, 1);
            }
        }

        return result;
    }
}

直覺想 就用 計數器去實作了，但這樣的算法
這麼做的時間複雜度為O(n)，空間複雜度亦為O(n)

以下 都不是我寫的，純粹學習

看到一種一行的寫法，其意涵為majority element一定會通過中間的位置。那定義就會叫過半數吧XD

public class Solution 
{
    public int MajorityElement(int[] nums) 
	=>nums.GroupBy(x => x).Select(x => new { x.Key, c = x.Count()}).OrderByDescending(x => x.c).FirstOrDefault().Key;
}

寫法2

public class Solution {
    public int MajorityElement(int[] nums) {
        //return nums.ToList().GroupBy(x => x).OrderByDescending(g=>g.Count()).Select(y=>y.Key).FirstOrDefault();
        Array.Sort(nums);
        return nums[nums.Length/2];
    }
}

Time complexity:
O(nlog(n))

• Space complexity:
  No extra space is used

最想瞭解:

public class Solution {
    public int MajorityElement(int[] nums) {
        int count = 0;
        int? candidate = null;

        foreach (int num in nums) {
            if (count == 0) candidate = num;
            count += (num == candidate) ? 1 : -1;
        }

        return candidate.Value;
    }
}

• Time complexity:
  O(n)
• Space complexity:
  O(1)

ChatGPT版本

using System;

class Program
{
    static int MajorityElement(int[] nums)
    {
        int count = 0;
        int candidate = 0;

        foreach (int num in nums)
        {
            if (count == 0)
                candidate = num;

            if (num == candidate)
                count++;
            else
                count--;
        }

        return candidate;
    }

    static void Main(string[] args)
    {
        int[] nums = { 2, 2, 1, 1, 1, 2, 2 };
        int majority = MajorityElement(nums);

        Console.WriteLine("Majority element: " + majority);
    }
}

說明如下:
Boyer-Moore投票算法（Boyer-Moore Voting Algorithm）是一種用於在一個具有大量元素的列表中查找多數元素的有效方法。該算法的時間複雜度為O(n)，其中n是列表的大小。該算法是由Robert S. Boyer和J Strother Moore於1981年提出的。

算法的基本思想是假設列表中的一個元素為多數元素，然後進行遍歷，對於每個元素，如果與候選元素相同，就將候選元素的計數器加1，否則減1。如果計數器為0，則將候選元素更換為當前元素。最後剩下的候選元素就是多數元素。

Reference:

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

https://ithelp.ithome.com.tw/articles/10213285