Skip to content

Latest commit

 

History

History
256 lines (212 loc) · 5.8 KB

0169._majority_element.md

File metadata and controls

256 lines (212 loc) · 5.8 KB
Raw

Navigation

Links:

  1. https://leetcode.com/problems/majority-element/
  2. https://leetcode-cn.com/problems/majority-element/

Solution 1 暴力法，一般会超时

用一个循环遍历整个列表，然后用另外一个循环统计每个数字出现的次数。 时间复杂度：O(N^2)。 空间复杂度：O(1)

class Solution:
    def majorityElement(self, nums):
        majority_count = len(nums) // 2

        for num in nums:
            count = sum(1 for elem in nums if elem == num)
            if count > majority_count:
                return num

Solution 2 计数

时间复杂度：O(N)。 空间复杂度：O(N)

std_lib collections.Counter(哈希表，以空间换时间)

import collections

class Solution:
    def majorityElement(self, nums):
        counts = collections.Counter(nums)  # issubclass(collections.Counter, dict) -> True
        
        if counts:
            return counts.most_common()[0][0]
class Solution:
    def majorityElement(self, nums):
        counts = collections.Counter(nums)
        return max(counts.keys(), key=counts.get)

原生dict(哈希表，以空间换时间)

class Solution:
    def majorityElement(self, nums):
        counter = {}

        for num in nums:
            if num not in counter:
                counter[num] = 1
            
            if counter[num] > len(nums) // 2:
                return num
            else:
                counter[num] += 1
class Solution:
    def majorityElement(self, nums):
        counter = {}

        for num in nums:
            counter.setdefault(num, 1)
            
            if counter[num] > len(nums) // 2:
                return num
            else:
                counter[num] += 1

用set处理后得到唯一的数字，然后计数

class Solution:
    def majorityElement(self, nums):
        nums_set = set(nums)
        
        for num in nums_set:
            if nums.count(num) > len(nums) // 2:
                return num

Go

func majorityElement(nums []int) int {
	m := make(map[int]int, len(nums))
	half_len := len(nums) / 2

	for _, v := range nums {
		m[v] += 1

		if m[v] > half_len {
			return v
		}
	}

	return 0

}

Solution 3 排序

sorted用的是timsort。 时间复杂度：O(N * log(N))。 空间复杂度：O(N)。 即使是极端情况，数组中索引为n // 2的数字和众数重叠。

class Solution:
    def majorityElement(self, nums):
        return sorted(nums)[len(nums) // 2]

Go

package main

import "sort"

func majorityElement(nums []int) int {
	sort.Ints(nums)

	return nums[(len(nums)-1)/2]
}

Solution 4 随机化

和Solution 3的前提一样，即使是极端情况，数组中索引为n // 2的数字和众数重叠。 时间复杂度：最差为O(无穷大)。一般为O(N)线性。 空间复杂度：O(1)

import random

class Solution:
    def majorityElement(self, nums):
        majority_count = len(nums)//2
        
        while True:
            candidate = random.choice(nums)
            if sum(1 for elem in nums if elem == candidate) > majority_count:
                return candidate

Solution 5 分治

求左右两边的局部众数，就可以求全局的众数。 时间复杂度：O(N * logN) 空间复杂度：O(logN)。因为每次分开两半。数组长度变为1之前有O(logN)次切断，每次用系统栈保存。

class Solution:
    def majorityElement(self, nums):
        if len(nums) == 1:
            return nums[0]

        left = self.majorityElement(nums[len(nums)//2:])
        right = self.majorityElement(nums[:len(nums)//2])

        return [left, right][nums.count(right) > len(nums) // 2]

Solution 6 Boyer-Moore投票算法（抵消）

非众数和众数抵消，活下来的就是众数 时间复杂度：O(N) 空间复杂度：O(1)

class Solution:
    def majorityElement(self, nums):
        count = 0
        candidate = None

        for num in nums:
            if count == 0:
                candidate = num
            count += 1 if num == candidate else -1

        return candidate

Go

package main

func majorityElement(nums []int) int {
	count := 0
	candidate := 0

	for _, v := range nums {
		if count == 0 {
			candidate = v
		}

		if v == candidate {
			count++
		} else {
			count--
		}
	}

	return candidate

}

Solution 7 用栈去实现抵消

时间复杂度：O(N) 空间复杂度：O(N)

class Solution:
    def majorityElement(self, nums):
        stack = []

        for num in nums:
            if not stack or num == stack[-1]:  # 栈为空或者当前数字等于栈顶元素
                stack.append(num)
            else:
                stack.pop()

        return stack[-1]

Go

package main

func majorityElement(nums []int) int {
	stack := make([]int, 0, len(nums))

	for _, v := range nums {
		length := len(stack)
		if length ==  0 || v == stack[length-1] {
			stack = append(stack, v)
		} else {
			stack = stack[:length-1]
		}
	}

	return stack[len(stack)-1]
}