【五种方法解决】找出数组中出现次数超过数组长度一半的数字 |
您所在的位置：网站首页 › java找出出现次数最多的数字的函数 › 【五种方法解决】找出数组中出现次数超过数组长度一半的数字 |
|
剑指offerJZ28:数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。 这道题是在面试时常问的一道题，有多种解法，我们分别看一下； 方法一：利用map利用map的key -value模型来存放arr[i]和相对应出现的次数，最后用次数去跟数组长度一半去比较，大于则就是；比如1,2,3,2,2,2,5,4,2；就是1出现一次、2出现5次、3.4.5各出现一次；返回的就是2； public static int solution1(int[] arr){ //利用map的key value模型来存放arr[i]和相对应出现的次数 HashMap map=new HashMap(); for(int i=0;iarr.length/2){ return entry.getKey(); } } return 0; } 方法二：排序求中间值出现的次数超过长度一半，那给数组排序以后，它一定处在最中间的位置；比如1,2,3,2,2,2,5,4,2排完序是1,2,2,2,2,2,3,4,5,；接下来去统计数组中跟arr[mid]值一样的元素，相等count++;如果count的值大于mid，则说明存在输出，否则返回0； public static int solution2(int[] arr){ //先对数组排序，如果这个数存在，那它一定在arr[mid]的位置， Arrays.sort(arr); int count=0; int mid=arr.length/2; for(int i=0;imid){//出现的次数超过mid，则返回它； return arr[mid]; } return 0; } 方法三：抵消法将target和其他元素进行抵消，由于target出现的次数大于别的元素，所以最后剩下的就是我们要找的；在遍历数组的时候保存两个值：数组中的一个元素(target) 和 该元素出现的次数(times)。当我们遍历到下一个元素的时候，如果下一个元素和我们之前保存的元素相等，则次数加1，如果下一个元素和我们之前保存的元素不相等，则次数减1。如果次数为零，我们需要保存下一个元素，并且把次数重设为1。由于目标元素出现的次数比其它所有元素出现的次数之和还要多，所以目标元素肯定是最后一次把次数设为1时对应的元素。 * public static int solution3(int[] arr){ //抵消法：将target和其他元素进行抵消，由于target出现的次数大于别的元素，所以最后剩下的就是我们要找的 //1,4,5,7,2,4,5,4,6,4,5,4,4,4,4 int target=arr[0];//target先设为arr[0]; int times=1; for(int i=0;i |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |