有關(guān)遞歸與分治的做題筆記，Python實(shí)現(xiàn)
169. 求眾數(shù) Majority Element
第一種方法：兩重循環(huán)暴力求解
第二種方法：哈希表記錄每個(gè)元素出現(xiàn)次數(shù)靖秩，發(fā)現(xiàn)出現(xiàn)超過n/2的就是眾數(shù)
class Solution:
def majorityElement(self, nums: List[int]) -> int:
leng = len(nums)
if leng == 1:
return nums[0]
dic = {}
for i in nums:
if i in dic:
dic[i] += 1
if dic[i] >= leng / 2:
return i
else:
dic[i] = 1
第三種方法：排序后直接返回中間值州藕，因?yàn)轭}目限定條件必然存在眾數(shù)
def majorityElement(self, nums: List[int]) -> int:
return sorted(nums)[len(nums)//2]
第四種方法：用list.count()方法
def majorityElement(self, nums: List[int]) -> int:
# 此處如果遍歷整個(gè)nums會超時(shí)
for i in nums[len(nums)//2:]:
if nums.count(i) > len(nums)//2:
return i
第五種方法：分治
def majorityElement(self, nums):
if not nums:
return None
if len(nums) == 1:
return nums[0]
a = self.majorityElement(nums[:len(nums)//2])
b = self.majorityElement(nums[len(nums)//2:])
if a == b:
return a
return [b, a][nums.count(a) > len(nums)//2]
# 這個(gè) return 的寫法等同于下面的 if else
# 因?yàn)槿艉笠粋€(gè)[]里為True即1所以取[b,a][1]=a, False即0取[b,a][0]=b
#
# if nums.count(a) > len(nums)//2:
# return a
# else:
# return b
