第十一天 Majority Element

哈哈，继续开始刷水题

今天比较丢人，开始选的那道题，因为对位运算不是太熟，有个思路，但没深入去想，就轻易但放弃了，那么就选了道更水的题目：

https://leetcode-cn.com/problems/majority-element/description/

求众数，就是在一个数组中，出现次数最多的那个数字。

嗯，上来，就可以很“勇猛”的想到，用一个字典来保存每个数字和他出现的次数，每次这个次数增加的时候，就会看一下他是否过半，如果是的话就可以直接返回结果了。

思路非常直接，有效，当然要考虑一下特殊情况，就是只有一个元素的时候，就直接返回呗。

好代码就更直接了：

class Solution:
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 1:
            return nums[0]
        half = len(nums)/2
        map = {}
        for i in range(len(nums)):
            if nums[i] in map:
                map[nums[i]] += 1
                if map[nums[i]] >= half:
                    return nums[i]
            else:
                map[nums[i]] = 1

自己看完，都觉得是浓浓的Java风格，哎，写了十几年，实在有点改不过来了。

苦思冥想了下，稍微改成了比较pythonic的风格了：

class Solution:
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        temp = list(set(nums))
        for i in temp:
            if nums.count(i)>len(nums)/2
              return i

这里主要是利用了list和set这两个内置函数，然后还有就是数组的count方法，嗯，这里感觉python提供了好多遍历的，我都不知道或是不会用，嗯，还是做的时候慢慢学吧，当然还应该有更pythonic的写法了，毕竟还是刷算法题为主，就不继续往下了

那么是否还有更好和优雅的方法呢？其实是有的，我可以把数组拍个序，这个时候出现次数超过一半的数字，中间那个元素肯定是，因为他不管是前一半还是后一半，都出现超过一半，所以就可以直接取中间那个数字的

这个会代码可以简单了，不风骚的话，两行就搞定。

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

这里要特别注意是用 // 整除，不能用/ 否则返回的是float，就尴尬了

好，这道题尽管不难，但要能深挖的话，还是有不少好玩的