天天看点

leetcode面试题 17.10. 主要元素

题目要求:

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      
leetcode面试题 17.10. 主要元素