《剑指offer》数组中出现次数超过数组长度一半的数字
程序员文章站
2022-04-14 13:25:23
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。 ......
题目:
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。
解析:
看到这道题我首先想到先给数组排序,在遍历一遍查找已经排好序的数组中的符合题意的数。这种方法是可行的,但是这种方法太明显了,而且排序时间复杂度大于O(n),感觉面试官肯定不会同意。于是我想到了用第i个数与i+1个数进行比较,如果相同则记下此数并且计数器加一,不同就减一,当计数器为零时,重新记下这个数;一遍遍历完毕,如果计数器为零则没有这样的数,否则有可能存在,再遍历一遍,将记录的数字与数组所有数字比较,最后如果相同的数字大于数组长度一般则返回该数,反之返回0,这种方法的时间复杂度为O(n);
下面我把两种方法的代码都写下来了分享给大家。
方法一代码:
1 int MoreThanHalfNum_Solution(int *arr,int len) 2 { 3 int i,j,flag = 1,count = 1; 4 for (i=0; i<len-1; i++) //给数组排序 5 { 6 for (j=0; j<len-1-i; j++) 7 { 8 if (arr[j]>arr[j+1]) 9 { 10 int tmp = arr[j]; 11 arr[j] = arr[j+1]; 12 arr[j+1] = tmp; 13 flag = 0; 14 } 15 } 16 if (flag) 17 break; 18 } 19 for (i = 0; i<len; i++) //遍历一遍查找是否有符合题意的数字 20 { 21 if (arr[i] == arr[i+1]) 22 { 23 j = i; 24 count++; 25 if (count>(len>>1)) 26 { 27 return arr[j]; 28 } 29 } 30 else 31 { 32 count = 1; 33 } 34 } 35 return 0; 36 }
方法二代码:
1 int MoreThanHalfNum_Solution(int *arr,int len) 2 { 3 int i = 1; 4 int k = 0; 5 int count = 1; 6 while (i<len) 7 { 8 if (arr[i]==arr[k]) 9 { 10 k = i; //记录当前位置 11 count++; 12 } 13 else 14 { 15 count--;//不同则计数器减1 16 if (count == 0) 17 { 18 count = 1; 19 k = i; 20 } 21 } 22 i++; 23 } 24 if (count) 25 { 26 count = 0; 27 for (i=0; i<len; i++) 28 { 29 if(arr[k]==arr[i]) 30 count++; 31 } 32 if (count>len/2) 33 return arr[k]; 34 else 35 return 0; 36 } 37 else 38 return 0; 39 }
CSDN博客地址:http://blog.csdn.net/qq_38646470
上一篇: Python3 文件系统
下一篇: python实现自动打卡小程序
推荐阅读
-
剑指offer28:找出数组中超过一半的数字。
-
PHP实现找出数组中出现次数超过数组长度一半的数字算法示例
-
[PHP] 算法-数组中出现次数超过一半的数字的PHP实现
-
数据结构算法(数组中出现次数超过一半的数字)
-
【剑指 Offer-python】 03. 数组中重复的数字
-
php实现数组中出现次数超过一半的数字的统计方法
-
剑指offer 56 数组中数字出现的次数 lintcode 82. 落单的数、83. 落单的数 II、84. 落单的数 III
-
【剑指offer】面试题56(1):数组中只出现一次的两个数字
-
剑指offer:数组中只出现一次的两个数字(java版)
-
剑指offer 面试题56 python版+解析:数组中只出现一次的两个数字,数组中唯一只出现一次的数字