day25 多數元素(leetcode)

169. 多數元素

給定一個大小為 n 的數組，找到其中的多數元素。多數元素是指在數組中出現次數 大于 ⌊ n/2 ⌋ 的元素。

你可以假設數組是非空的，并且給定的數組總是存在多數元素。

示例 1：
輸入：[3,2,3]
輸出：3
           

示例 2：
輸入：[2,2,1,1,1,2,2]
輸出：2
           

進階：

嘗試設計時間複雜度為 O(n)、空間複雜度為 O(1) 的算法解決此問題。

解題

1. 哈希計數

直接用哈希表計數，傳回大于

n/2

的元素

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        dic = {}
        for element in nums:
            if element in dic:
                dic[element] += 1
            else:
                dic[element] = 1
            if dic[element] > len(nums)/2:
                return element
           

2. 排序

因為清單中一半以上的元素都是“多數元素”，是以我們發現，如果清單有序，那其最中間的元素一定是該“多數元素”。

是以我們選擇對清單排序并傳回位于清單中間的元素

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums.sort()
        return nums[len(nums)//2]
           

3.中位數

雖然排序很快，也不需要額外的空間，但是時間卻達不到O(n)

但是從排序的思想中，我們可以發現，我們真正需要的數隻是“有序清單中位于中間的數”即 “中位數” 。

是以，我們并不關心清單的其他位置有不有序。這樣，我們可以節省大量的時間。

參照快排的思想，我們對快排做一個簡化