多数元素

1. 题目描述

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

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

2. 思路

1. 思路一
   • 使用map统计每个元素的个数
   • 遍历map找出个数>n/2的元素
2. 思路二
   • 遍历数组，如果当前数和下一个数相同，那么次数+1，否则-1，减为0时重新开始
   • 重新遍历一遍，统计一下这个数字的个数，是否>n/2

3. 实现

3.1. map

func majorityElement(nums []int) int {
    count := make(map[int]int, 0)
    for _, num := range nums {
        count[num]++
    }
    for k,v := range count {
        if v > len(nums)/2 {
            return k
        }
    }
    return 0
}

3.2. 相同+1，不同-1

func majorityElement(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	count := 1
	num := nums[0]
	for i := 1; i < len(nums); i++ {
		if num == nums[i] {
			count++
		}else {
			count--
        }
        if count == 0 {
            num = nums[i]
            count = 1
        }

	}
	count = 0
	for _, val := range nums {
		if val == num  {
			count++
		}
	}
	if count > len(nums) /2 {
		return num
	}
	return 0
}

4. 参考

• 169. 多数元素 - 力扣（LeetCode）