169. 多数元素

解法一：暴力，两层循环，计算每个元素出现的次数，然后对比一下即可。

时间复杂度：O(N ²)

解法二：计数优先考虑 MAP，空间换时间，一遍遍历使用 MAP 计数，再对 MAP 中的元素进行比较，比较时次数少于 N。

时间复杂度：O(N) ，空间复杂度 O(N)

解法三：排序，排序后，最多数字一定是连续的，此时返回第 N/2的元素则一定是众数。

时间复杂度：O(NlogN) = 排序快排 O(NlogN)

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

解法四：分治。因为这里众数是一定存在的，所以逻辑上可以简化。

原理：和 pow 一样，分成两份，分别找左右两份中出现次数最多的数，如果 left中的众数 == right 中的众数，则众数返回任意一个即可。如果相等不成立，就比较左右众数的次数，返回次数最多的那个数。

class Solution {
    fun majorityElement(nums: IntArray): Int {
        return findElement(nums, 0, nums.size - 1)
    }

    fun findElement(nums: IntArray, lPos: Int, rPos: Int): Int {
        //临界值 只有一个元素时直接返回
        if (lPos == rPos) return nums[lPos]
        //取中点
        val mid = (rPos - lPos) / 2 + lPos
        
        val left = findElement(nums, lPos, mid)
        val right = findElement(nums, mid + 1, rPos)
        //左右众数一致 随意返回一个
        if (left == right) return left
        //不一致则 比较count 大的则为众数
        return if (count(left, nums, lPos, rPos) > count(right, nums, lPos, rPos)) { left } else { right }
    }

    fun count(num: Int, nums: IntArray, lPos: Int, rPos: Int): Int {
        var count = 0
        for (i in lPos..rPos) {
            if (nums[i] == num) count++
        }
        return count
    }
}