Majority Element

题目描述

多数元素：

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

假定数组非空，并且总是存在多数元素。

示例：

输入：[3, 2, 3]
输出：3

解法

解法一：排序法：

• 时间复杂度：O(nlogn)，依赖具体的排序算法，通常使用的是O(nlogn)复杂度的算法。

• 空间复杂度：依赖具体的排序算法。

func majorityElement(nums []int) int {
    sort.Ints(nums)
    return nums[len(nums)/2]
}

解法二：随机法

• 时间复杂度：O(n)

• 空间复杂度：O(1)

func majorityElement(nums []int) int {
    rand.Seed(int64(time.Now().Unix()))
    for {
        candicate := rand.Intn(len(nums))

        total := 0
        for _, v := range nums {
            if v == nums[candicate] {
                total++
            }
            if total > len(nums)/2 {
                return v
            }
        }
    }
}

解法三：哈希法

• 时间复杂度：O(n)

• 空间复杂度：O(n)

func majorityElement(nums []int) int {
    cMap := map[int]int{}
    max := 0
    index := 0
    for i, v := range nums {
        cMap[v]++
        if cMap[v] > max {
            max = cMap[v]
            index = i
        }
    }
    return nums[index]
}

解法四：投票法

• 时间复杂度：O(n)

• 空间复杂度：O(1)

func majorityElement(nums []int) int {
    candicate := 0
    total := 0
    for _, e := range nums {
        if total == 0 {
            candicate = e
            total++
            continue
        }
        if e == candicate {
            total++
        } else {
            total--
        }
    }
    return candicate
}

解法五：位运算

• 时间复杂度：O(n)

• 空间复杂度：O(1)

func majorityElement(nums []int) int {
    result := 0
    for i := 0; i < 64; i++ {
        one := 0
        for _, ele := range nums {
            if (ele>>i)&1 == 1 {
                one++
            }
        }
        if one > len(nums)/2 {
            result += (1 << i)
        }
    }
    return result
}

解法六：分治法

• 时间复杂度：O(nlogn)

• 空间复杂度：O(logn)

func majorityElement(nums []int) int {
    if len(nums) == 1 {
        return nums[0]
    }

    leftMajor := majorityElement(nums[0 : len(nums)/2])
    rightMajor := majorityElement(nums[len(nums)/2:])

    if leftMajor == rightMajor {
        return leftMajor
    }

    var leftCnt, rightCnt int
    for _, ele := range nums {
        if ele == leftMajor {
            leftCnt++
        }
        if ele == rightMajor {
            rightCnt++
        }
    }

    if leftCnt > rightCnt {
        return leftMajor
    }
    return rightMajor
}