【LeetCode】【Kotlin】169. Majority Element

題意

給予 nums 數字 array ，大小為 n，在此之中，有超過 n/2 的元素都是某個同樣的數字，請找出那個數字是甚麼。

題解

因為那個數字一定會佔據一半以上的空間，所以在對 array 進行排序之後，即使那個數字是從最前面或最後面開始排，array 的第 n/2 個元素，都一定是它。

程式碼

class Solution {
    fun majorityElement(nums: IntArray): Int {
        nums.sort()
        return nums[nums.size / 2]
    }
}

216ms / 42.81MB (beats 79.62% / 11.89%)

其他 : Moore Voting Algorithm

將第一個遇到的數設為目標，若之後遇到與目標相同的數，就把 count++，否則 count--。若 count 被減至0，則改目標為下個數。

最後留下的目標就是答案。

(私以為這個算法滿酷的。不會特別想用，不過若使用這種方式，只需要遍歷一輪數組，不需要對數組排序。)

(以上方法都僅適用於目標數字會佔據 array 一半以上的情況。)