【题目描述】
Given an array of integers, the majority number is the number that occurs more than half of the size of the array. Find it.
Notice:You may assume that the array is non-empty and the majority number always exist in the array.
给定一个整型数组,找出主元素,它在数组中的出现次数严格大于数组元素个数的二分之一。
注意:你可以假设数组中没有非空和主元素。
【题目链接】
【题目解析】
最直观的想法就是,建立HashMap,记录list中的每一个integer元素的个数,如果大于1/2 list长度,即可返回。
进一步分析发现,其实并不需要记录所有的integer元素的个数,可以只记录当前最多的那一个majority。这种方法也称为: Boyer–Moore majority vote algorithm
换一种角度,是否可以直接从list中读取这个majority呢?如果对list进行排序,那么1/2处的元素,也就是majority的那个integer了。当然这种方法有个问题,就是对于没有majority的情况下(没有一个达到了1/2 总长度),是无法判断是否存在majority的,如果题目中明确一定存在这样的majority,那么这种方法也是可行的。
时间 O(n), 空间 O(1)
【参考答案】
评论
发表评论