優質文章，第一時間送達！

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

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

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

關于題目

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

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

示例 1:

輸入: [3,2,3]

輸出: 3

示例 2:

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

輸出: 2

暴力解法

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

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的長度，然后進行for循環嵌套最終獲取結果。這種時間復雜度：O(n*n)的解法就不多贅述了。主要看看下面兩種解法。

哈希表

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

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

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

不知道max有key這個參數的，舉個手，讓我知道我不是一個人，哈哈…

奇思妙想

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

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

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

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

本文為企業推廣，本網站不做任何建議，僅提供參考，作為信息展示！

推薦閱讀：蘋果x與xr