首页 > 代码库 > 数组中出现次数超过一半的数字
数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。
例如输入数组:{1,3,3,2,3,2,3,3,2}。由于2在数组中出现了5次,超过数组长度的一半,因此要输出2。
有两种解法:
第一种方法是基于快速排序算法的原理,边排序边判断是否符合输出条件。这种方法的代码我因为没有保存,在电脑蓝屏之后全部消失了·······~~~~(>_<)~~~~ 呜呜。
第二种方法是根据数组特点找出的算法,时间复杂度为O(n),且不用改变数组本身结构。
思想是:如果一个数出现的次数超过数组一半的长度,那么就是说出现的次数比其他所有数字出现的次数还要多。因此我们可以考虑保存2个值,一个是数组中的一个数,一个是数的次数。当我们遍历到下一个数字的时候,如果下一个数字和我们之前保存的数字相同,则次数加1,如果不同则次数减1。如果次数为0了这保存当前遍历到的数,并把次数设为1。遍历完整个数组之后,返回当前保存的数字,即是我们要找的数字。
代码如下:
1 int MoreThanHalfNum(int* numbers, int length) 2 { 3 int result = numbers[0]; 4 int time = 1 ; 5 for (int i = 1 ;i < length ; i++) 6 { 7 if (0 == time) 8 { 9 result = numbers[i] ; 10 time++ ; 11 } 12 else if (numbers[i] == result) 13 { 14 time++; 15 } 16 else 17 { 18 time-- ; 19 } 20 } 21 return result ; 22 } 23 int main() 24 { 25 int numbers[] = {1,3,3,2,3,2,3,3,2}; 26 cout<<MoreThanHalfNum(numbers, 9); 27 getchar(); 28 return 0; 29 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。