例如#xff1a;输入如下所示的一个长度为9…内容1.数组中出现次数超过一般的数字2.数组中出现一次的数字3.颜色分类问题

这是剑指offer中的一道题目数组中有一个数字出现的次数超过数组长度的一半请找出这个数字。

例如输入如下所示的一个长度为9的数组{1,2,3,2,2,2,5,4,2}。

由于数字2在数组中出现5次超过了数组长度的一半因此输入2如果不存在则输出0。

对于没有思路的问题我们的策略都是先在脑子里快速过一遍常见的数据结构和常见的算法策略看看谁能帮我们解决问题所以很多问题就会自然而然的出现多种解法。

首先用排序行不行这里说一定存在出现次数超过一半的数字了那么先对数组进行排序。

在一个有序数组中次数超过一半的必定是中位数所以可以直接去出中位数。

如果不放心可以再遍历数组确认一下这个数字是否出现次数超过一半。

OK没问图第一种方法就出来了。

这种方法的时间复杂度取决于排序算法的时间复杂度最快的为O(nlogn)。

由于排序的代价比较高所以我们继续找其他方法。

其次用Hash行不行我们先创建一个HashMap的key是元素的值value是已经出现的次数然后遍历数组来统计所有元素出现的次数。

最后再遍历Hash找到出现次数超过一半的数字。

OK第二种方法出来了。

方法一

{if(arraynull||array.length0)return

0;int

i1;ilen;i){if(times0){resultarray[i];times1;continue;}if(array[i]result)times;elsetimes--;}times0;for(int

i0;ilen;i){if(array[i]result)times;if(timeslen/2)return

result;}return

(!set.add(i))//添加不成功返回false前加上运算符变为trueset.remove(i);//移除集合中与这个要添加的数重复的元素}//注意边界条件的处理if

(set.size()

null;//如果Set集合长度为0返回null表示没找到return

set.toArray(new