2.1 大于n/k次的元素
题目描述：给一个整数数组，找出所有出现次数大于n/3的元素。
Input: nums = [3,2,3]
Output: [3]
摩尔投票法： 一般情况一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/k ⌋ 次的元素。n/k的众数最多只有k - 1个，原因：假设有k个众数，则 出现次数（⌊ n/k ⌋ +1） × \times× 众数个数 k > n。
思路：此题为例 k = 3, 则最多有2个出现次数大于n/3的元素，把此情景想像成在大会中投票选出两个候选者， 则有两个候选 n1 和n2。
- 如果投n1（当前元素等于n1），则n1的票数 c1++;
- 如果投n2（当前元素等于n2），则n2的票数c2++;
- 如果n1,n2都不投（即当前值与n1，n2都不相等）,那么检查此时n1或n2的票数是否为0：
- 如果为0,则当前元素成为新的候选人替代掉票数为0的人；
- 如果n1,n2两个人的票数都不为0，那么n1,n2两个候选人的票数均减一；
最后会有这么几种可能：有2个大于n/3，有1个大于n/3，有0个大于n/3，遍历结束后选出了两个候选人，但是这两个候选人是否满足> n/3，还需要再遍历一遍数组，找出两个候选人的具体票数，因为不一定有。
参考原文
示例代码：
func majorityElement(nums []int) []int {
v1, c1, v2, c2 := 0, 0, 0, 0
for _, n := range nums {
if n == v1 {
c1++
} else if n == v2 {
c2++
} else {
if c1 == 0 {
v1 = n
c1++
} else if c2 == 0 {
v2 = n
c2++
} else {
c1--
c2--
}
}
}
r := make([]int, 0)
c1, c2 = 0, 0
for _, n := range nums {
if n == v1 {
c1++
}
if n == v2 && v2 != v1 {
c2++
}
}
if c1 > len(nums) / 3 {
r = append(r, v1)
}
if c2 > len(nums) / 3 {
r = append(r, v2)
}
return r
}
2.2 缺失的第一个正数
题目描述：给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
进阶：实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案
思路：长度为N的整数数组，没有出现的最小正整数一定在[1, N + 1]。
方法1：最容易的做法用一个额外的哈希表记录出现的数字，然后从1遍历到N+1，根据hash表如果出现缺失就返回。但是该方法空间复杂度为O(n)。
示例代码：
func firstMissingPositive(nums []int) int {
m := map[int]bool{}
for _, n := range nums {
m[n] = true
}
for i := 1; i <= len(nums); i++ {
if m[i] == false {
return i
}
}
return len(nums) + 1
}
方法2：在原数组上建哈希表，因为结果只需要判断[1, N]的数，因此可以以负数当做标记（参考LeetCode官方题解）。
- 将数组中所有小于等于 0 的数修改为 N+1
- 遍历每一个数x，可能已经打过标记，因此原值为|x|，如果|x|在[1, N]范围，则给数组nums[|x| - 1]元素加上负号，已加过的不能再加。
- 遍历数组检查，如果值非负数返回i + 1，全为负数返回N+1
示例代码:
func IntAbs(x int) int {
if x < 0 {
return -x
}
return x
}
// 只关注正整数，用"-"号做标记
func firstMissingPositive(nums []int) int {
n := len(nums)
// 预处理，将元素全部变为整数
for i, v := range nums {
if v <= 0 {
nums[i] = n + 1
}
}
// 打标记
for i := 0; i < n; i++ {
x := IntAbs(nums[i])
if x <= n && nums[x - 1] > 0 {
nums[x - 1] *= -1
}
}
// 检查标记
for i := 0; i < n; i++ {
if nums[i] > 0 {
return i + 1
}
}
return n + 1
}
方法3：置换，将数组恢复成形如[1, 2, ... , N]的形式，即nums[i-1]=i（参考LeetCode官方题解）。
- 设v = nums[i], 如果nums[i] == nums [v-1]，则不需要置换，否则将nums[v-1]设为v，此时要先把nums[v-1]的值保存到nums[i]，此时v-1已经是正确的位置，但是i不一定是正确的位置，需要继续置换。
- 检查每个位置的值是否正确，全部正确返回N+1，否则返回i+1
示例代码:
func firstMissingPositive(nums []int) int {
n := len(nums)
for i, v := range nums {
for v > 0 && v < n + 1 && nums[i] != nums[v - 1] {
nums[v - 1], nums[i] = v, nums[v - 1]
v = nums[i]
}
}
for i, v := range nums {
if v != i + 1 {
return i + 1
}
}
return n + 1
}
