【题目描述】
Given an array of integers and a number k, the majority number is the number that occurs more than 1/k of the size of the array.Find it.
Notice:There is only one majority number in the array.
给定一个整型数组,找到主元素,它在数组中的出现次数严格大于数组元素个数的1/k。
注意:数组中只有唯一的主元素
【题目链接】
【题目解析】
依然抵消法,但是为了更快的获取,消除,增加次数,这里应该用hashtable(dictionary in python)
然后在剩下的数中找到出现次数最多的数,就是majority number(因为前提是只有一个majority number)
如果不确定,可以再loop一次找出这个数的出现次数
【参考答案】
评论
发表评论