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)
    // 預處理，將元素全部變?yōu)檎麛?    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不一定是正確的位置，需要繼續(xù)置換。
• 檢查每個位置的值是否正確，全部正確返回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
}