关于java:offer-39-数组中出现次数超过一半的数字

42次阅读

共计 366 个字符,预计需要花费 1 分钟才能阅读完成。

数组中呈现次数超过一半的数字


数组中呈现次数超过一半的数字”简称为“众数”。

题解

排序

数组中点的元素 肯定就是超过数组长度一半的那个元素,依照从小到大排列

这个办法有点秀

哈希表统计法 键值对

getOrDefault(Object key, V defaultValue) 

这个函数是如果 map 中存在这个 key,那就返回这个 key 自身的 value,如果不存在这个 key,那就返回这个 key 默认的 defaultValue,也就是这个函数键前面带的那个 defaultValue
如果这个键的值超过了长度的一半,那就阐明就是这个键就是题目要求,因为只有一个元素能够超过数组长度的一半

摩尔投票法





这个投票法有意思

  • 因为题目说了肯定存在一个众数,如果题目没有说,如果可能不存在众数,那就须要重新考虑

  • 最初那个要加一个验证,看这个最初剩下的数,他的长度是不是大于数组的一半

正文完
 0