優(yōu)質(zhì)文章，第一時間送達(dá)！

Leetcode最新上線了手機(jī)版app，之前手機(jī)只能通過瀏覽器登錄網(wǎng)站學(xué)習(xí)，如今有app，閑了就可以瞅兩道題。今天等車的時候隨手翻了一道題

169. 多數(shù)元素 http://leetcode-cn.com/problems/majority-element/。

看了下是眾數(shù)問題，腦子簡單過了下大概思路，就準(zhǔn)備接著看其他題了。但想想還是看下別人是怎么做的吧，結(jié)果….

關(guān)于題目

給定一個大小為 n 的數(shù)組，找到其中的多數(shù)元素。多數(shù)元素是指在數(shù)組中出現(xiàn)次數(shù)大于 ? n/2 ? 的元素。

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

示例 1:

輸入: [3,2,3]

輸出: 3

示例 2:

輸入: [2,2,1,1,1,2,2]

輸出: 2

暴力解法

先來看看最簡單無腦的暴力解法，詳細(xì)大多數(shù)人都能想到該解題方式：

1class Solution:
2 def majorityElement(self, nums):
3 majority_count = len(nums)//2
4 for num in nums:
5 count = sum(1 for elem in nums if elem == num)
6 if count > majority_count:
7 return num

先計算列表1/2的長度，然后進(jìn)行for循環(huán)嵌套最終獲取結(jié)果。這種時間復(fù)雜度：O(n*n)的解法就不多贅述了。主要看看下面兩種解法。

哈希表

這種方法，在LeetCode上很常見，就是使用Counter的方式，生成針對元素與出現(xiàn)次數(shù)的字典，然后進(jìn)行計算。

1class Solution:
2 def majorityElement(self, nums):
3 counts = collections.Counter(nums)
4 return max(counts.keys, key=counts.get)

本來覺得沒什么特別，但當(dāng)看到return操作時，覺得自己幾年的Python都白學(xué)了。居然不知道m(xù)ax函數(shù)，具有key的方法…一直是用它來簡單的比較最大值。殊不知針對字典操作時，max可以通過定義key值來進(jìn)行動態(tài)比較。（類似的方法如sorted倒是經(jīng)常使用）…

不知道m(xù)ax有key這個參數(shù)的，舉個手，讓我知道我不是一個人，哈哈…

奇思妙想

最讓我佩服的就是下面這種解題思路，堪稱經(jīng)典。

文中定義有一個關(guān)鍵點，多數(shù)元素是指數(shù)據(jù)中出現(xiàn)大于n/2的元素。那么如果所有數(shù)字被單調(diào)遞增或者單調(diào)遞減的順序排了序，當(dāng)n是奇數(shù)時，眾數(shù)的下標(biāo)為n/2,當(dāng)n是偶數(shù)時，下標(biāo)為n/2 +1。于是出現(xiàn)了下面這種犀利的解法。

1class Solution:
2 def majorityElement(self, nums):
3 nums.sort
4 return nums[len(nums)//2]

然而，官方的答案還遠(yuǎn)不止這些，一共提供了六種解答方式。所以，你覺得自己Python學(xué)到位了嗎？

本文為企業(yè)推廣，本網(wǎng)站不做任何建議，僅提供參考，作為信息展示！

推薦閱讀：蘋果x與xr