今日题目(剑指Offer系列)
剑指 Offer 39. 数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。 你可以假设数组是非空的,并且给定的数组总是存在多数元素。
示例:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2
解题思路:
>该题目就是要找到数组中的超过一半的数字 >其实有一种最简单得方法就是将数组进行排序 >数组中间的值一定是超过一半的数字 >还有一种方法就是摩尔选票,什么意思? >就是一种不断抵消选票的原理 >先假设第一个是最终的结果, >遍历第二个元素时,如果与第一个相同就将选票+1 >否则将第一个人的选票抵消 >最终有票数的就是最多的人
Python解法:
class Solution: def majorityElement(self, nums: List[int]) -> int: res=0 tickets=0 for num in nums: if tickets==0: res=num if num==res: tickets+=1 else: tickets-=1 return res
Java解法:
class Solution { public int majorityElement(int[] nums) { int res=0; int tickets=0; for(int num:nums){ if(tickets==0){ res=num; } if(num==res){ tickets++; }else{ tickets--; } } return res; } }