数据结构2：数组

2.1 大于n/k次的元素

LeetCode No.229

题目描述：给一个整数数组，找出所有出现次数大于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：
  1. 如果为0,则当前元素成为新的候选人替代掉票数为0的人；
  2. 如果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 缺失的第一个正数

LeetCode No.41

题目描述：给你一个未排序的整数数组 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
}