1.问题描述：
给定一个大小为 n 的数组，找到其中的多数元素。
目录
1.问题描述：
2.解决思路（这里整理了两种方法以作参考：排序法+投票法）
3.程序代码：
4.小结
多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
（你可以假设数组是非空的，并且给定的数组总是存在多数元素。）
2.解决思路（这里整理了两种方法以作参考：排序法+投票法）
- 排序法：首先理解题目，多数元素是指出现次数大于n/2的元素，既然大于n/2，可想而知，一个数组中有且仅有这一个多数元素，再思考之，如若将这个数组元素按升序排序，那么最中间的元素一定是该多数元素，因为多数元素个数大于n/2，则最中间必然是该元素。这里是关键，要好好来理解，如若不懂，亦可多写几组数据排序后加以验证。
投票法：投票法是引用一个变量来进行类似投票计数的操作，如果赞成票，就+1，不赞成票就-1.什么意思呢，具体到这道题目，就是引入一个变量a，从数组从第一个元素开始，先假定第一个数就是被投票者，如果接下来又遇到这个数，就票数+1（即a+1），而如果遇到的不是这个数，相当于反对票，就票数-1（即a-1），因为要找的多数元素出现次数大于n/2，那么肯定只有这个多数元素的a值是大于0的。所以遍历的时候，当票数a为0时，就可以换下一个假定被投票者，当遍历完成后，谁的票数>0，谁就是要找的多数元素。
3.程序代码：
方法一：排序法
import java.util.Arrays;
import java.util.Scanner;
//给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
//你可以假设数组是非空的，并且给定的数组总是存在多数元素
//方法一：排序法
public class Array_Find_3_7 {
public static void main(String[] args) {
System.out.print("输入：");
// 从键盘输入数组
Scanner sc=new Scanner(System.in);
String str=sc.next();
String []arr=str.split(",");
int []a=new int[arr.length];
for (int i = 0; i < arr.length; i++) {
a[i]=Integer.parseInt(arr[i]);
}
// 因为题目假设一定存在多数元素，而多数元素又是出现次数大于n/2的，故将数组排序后，中间元素一定是那个数
Arrays.sort(a);
System.out.println("输出："+a[a.length/2]);
}
}
结果如下：
代码注意事项：
从键盘输入数组的方法：输入一组用逗号隔开的整数，先用字符串存，然后变为字符串数组，再把字符串数组转化为整型数组；
Arrays.sort(a)为调用方法对数组a进行排序操作（系统方法为快速排序，默认升序）；
方法二：投票法
public class Array_Find2_3_7 {
public static void main(String[] args) {
//给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数
//大于 ⌊ n/2 ⌋ 的元素。
int[]a=new int[]{1,1,1,1,2,4};
System.out.println(find(a));
}
public static int find(int[]arr){
int n=0;
Integer candidate=null;
for (int i = 0; i < arr.length; i++) {
if(n==0)
candidate=arr[i];
if(arr[i]!=candidate)
n--;
else
n++;
}
return candidate;
}
}
结果：
代码注意事项：投票法要设置两个变量，一个用于表示票数n,一个代表当前假定被投票人candidate;将candidate定义为Integer类是因为引用类型默认值为空
4.小结
排序法逻辑最简单，易于lijie，但投票法该种思想也很巧妙，值得学习借鉴。
