求众数

求众数1（leetcode）

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在众数。

示例 1:
输入: [3,2,3]
输出: 3

示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2

代码实现：

func majorityElement(_ nums: [Int]) -> Int {
    var dict = [Int: Int]()
    var num = nums[0]
    for i in nums {
        if dict[i] == nil {
            dict[i] = 1
        }
        else {
            var tmp = 1 + dict[i]!
            if tmp > nums.count/2 {
                num = i
                break
            }        
            dict[i] = tmp
        }
    }
        
    return num
}

 

求众数2（leetcode）

给定一个大小为 n 的数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1)。

示例 1:
输入: [3,2,3]
输出: [3]

示例 2:
输入: [1,1,1,3,3,2,2,2]
输出: [1,2]

分析：一个数组中，最多出现1个出现超过 ⌊ n/2 ⌋ 次的众数，最多出现2个出现超过 ⌊ n/3 ⌋ 次的众数

提示：摩尔投票算法：简单来说摩尔投票问题，找出一组数字序列中出现次数大于总数1/2的数字（并且假设这个数字一定存在）。显然这个数字只可能有一个。摩尔投票算法是基于这个事实：每次从序列里选择两个不相同的数字删除掉（或称为“抵消”），最后剩下一个数字或几个相同的数字，就是出现次数大于总数一半的那个

代码实现：

func majorityElement(_ nums: [Int]) -> [Int] {
        if nums.count < 2 {
            return nums
        }
        
        var m = 0, mc = 0
        var n = 0, nc = 0
        for i in nums {
            if i == m {
                mc += 1
            } else if i == n {
                nc += 1
            } else if mc == 0 {
                m = i
                mc += 1
            } else if nc == 0 {
                n = i
                nc += 1
            } else {
                mc -= 1
                nc -= 1
            }
        }
        
        mc = 0
        nc = 0
        
        for i in nums {
            if i == m {
                mc += 1
            } else if i == n {
                nc += 1
            }
        }
        
        var array = [Int]()
        if mc > nums.count/3 {
            array.append(m)
        }
        
        if nc > nums.count/3 {
            array.append(n)
        }
        return array
    }