关于golang:golangleetcode中级多数元素

第一题 少数元素

题目

简略的思路

简略的想法是应用哈希表或者排序实现

遍历一次数组，将每个数呈现的次数存入哈希表，当次数大于 n / 2 时返回即可
然而该计划空间复杂度为 O（n），不符合要求 O（1）

将数组排成有序数组，计算每个元素呈现的次数，当次数大于 n / 2 时返回即可
然而排序的工夫复杂度为 O（nlogn），大于题目要求 O（n）

随机法

分治法

代码.3

func majorityElement(nums []int) int {return majorityElementRec(nums, 0, len(nums) - 1)
}

// 判断众数
func countInRange(nums []int,  target int,lo int,  hi int) int{
    count := 0
    for  i := lo; i <= hi; i++ {if nums[i] == target {count++}
    }
    return count
}

// 二分查找
func majorityElementRec(nums []int,  lo int,  hi int) int{
    // 左边界等于右边界，只有一个元素，即为该数组众数
    if lo == hi {return nums[lo]
    }
    mid := (lo + hi) / 2
    // 左右众数
    leftMajority := majorityElementRec(nums, lo, mid)
    rightMajority := majorityElementRec(nums, mid + 1, hi)
    // 返回真正的众数
    if countInRange(nums, leftMajority, lo, hi) > (hi - lo + 1) / 2 {return leftMajority}
    if countInRange(nums, rightMajority, lo, hi) > (hi - lo + 1) / 2 {return rightMajority}
    return -1
}

摩尔投票法

代码

func majorityElement(nums []int) int {
    // 初始化
    candidate := -1
    count := 0

    for _, num :=range nums {
        // 如果相等，计数器加一
        if num == candidate {count++}else {
            // 否则计数器减一，消去一个非众数
            count--
        }
        // 初始化候选众数
        if count < 0 {
            candidate = num
            count = 1
        }
    }
    return candidate
}

成果

复杂度剖析

工夫复杂度：O(n)。Boyer-Moore 算法只对数组进行了一次遍历。

空间复杂度：O(1)。Boyer-Moore 算法只须要常数级别的额定空间。