leetcode面试题 17.10. 主要元素

题目要求：

关键在于时间复杂度在O(N)，每次只对数组做一次遍历

题解：

1.MAP

对数组进行一次遍历，记录数组中每个元素出现的次数并保存在map中，对map进行一次搜索，找到出现次数大于数组长度一半的主要元素

<1>map times初始为空，对数组nums进行遍历，若当前元素在times中不存在，则加入，若已经存在则其对应次数加一

<2>数组遍历结束后，遍历times，找到出现次数大于二分之一数组大小的元素，如果没有则返回-1

def majorityElement(self,nums):
    times = {}
    mylen = len(nums)
    for i in range(mylen):
        if nums[i] in times:
            times[nums[i]]+=1
        else:
            times[nums[i]]=1
    for i in range(mylen):
        number = times[nums[i]]
        if number>mylen//2:
            return nums[i]

    return -1      

2.摩尔投票算法

每次从数组中去掉两个不同的元素，最后剩余的元素就是主要元素或者是最后剩余的元素，结束后遍历一次数组，判断是否为主要元素。

<1>number用来记录数值，times记录出现次数。

<2>从数组第一位开始遍历，times=0说明遍历刚开始或者已经删除了一对不相等的元素，将数组当前元素赋给number

<3>若times不为0，判断nums[i]是否和number相等，不等则times-1，相当于删除nums[i]与一个number，相等则times+1，number出现次数加一。

<4>遍历一次后将得到一个number，再次遍历数组记录number出现次数，判断是否为主要元素。

def majorityElement(self,nums):
    number = 0
    times = 0
    for i in range(len(nums)):
        if times==0:
            number = nums[i]
            times = 1
        else:
            if number==nums[i]:
                times+=1
            else:
                times=times-1
    count = 0
    for i in range(len(nums)):
        if nums[i]==number:
            count=count+1
    if count>len(nums)/2:
        return number
    return -1