《剑指offer》数组中出现次数超过数组长度一半的数字
题目:
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为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
相关推荐
Laozizuiku 2019-11-02