问题描述

问题

有一个长度为n的数列，已知有一个数字出现的次数大于n/2，找出这个数字。

输入输出描述

例： 输入一个数组（假设：{1,3,2,2,2,4,2}） 输出： 数组为：{1,3,2,2,2,4,2} 众数为：2

 

思路

不妨把这个问题转换一下。假设有k个国家的士兵，一共n个人。其中有一个国家的士兵大于n/2，问这个国家是哪个。这样转换一下是不是生动多了？ 那这个国家应该怎么找呢，会是什么国家呢？ 。。。。。。。。。。。。。 开个玩笑。 比较容易想到的方法是一个一个去数，把同一个国家的士兵堆在一起，最后数一下那个国家的士兵最多。但是这样子时间复杂度非常高。 有个很简单的方法，既然是比哪个国家的士兵最多，那么不如。。。

我们不妨让他们“打一架”，两两配对，如果是不同国家的士兵，就让他们各自捅对方一刀，同归于尽。如实是同一个国家的士兵，就抱团一起去打别人。那么最后剩下来的士兵一定是来自士兵最多的那个国家的。 简称，同归于尽算法。

 

算法描述

先做一个标记，起始为数组的最左端。这个标记的左边为士兵的“尸体”，右边是还存活的士兵。标记命名为left。 从数组最左端开始向右逐个读取数字。         若当前读取的元素与下一个元素不同：                  则将下一个元素与left标记的元素互换位置，并将left标记右移一位。

 

程序实现

算法中涉及到数组元素交换的方法，所以我们先来写一个交换数组元素的方法：

/** * 交换数组中两个元素的位置 * @param a 数组 * @param i 其中一个元素的下标 * @param j 另一个元素的下标 */ private void exchange(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }

然后是算法主体部分：

/** * 找众数 * @description 已知某个数组长为n，其中有一个数字出现次数次数大于n/2，找出这个数字 * <br> * “同归于尽算法”： * <br> * 相邻的数字两两比较，将不同的数字“堆放”在数组最左边，最终剩下的数字就是众数 * @param a 数组 * @return 找到的众数 */ public int find(int[] a) { int left = 0; for (int i = 0; i < a.length - 1;i ++) { if (a[i] != a[i + 1]) //同归于尽 { exchange(a,left,i + 1); left += 2; } } return a[left]; }

这就完成啦。