算法题目
多数元素：给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [3,2,3]
输出: 3
示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2
思路分析：
解法1：暴力解法（双重循环）
思路：首席可以考虑暴力算法，用双重循环遍历数组可以得到每个数字的重复次数，在遍历中可以用一个变量来记录比较最大重复次数，另一个变量记录对应的数字，最后返回最大重复次数对应的数值。
分析：缺点就是时间复杂度为n平方，效率较低，优点就是思路简单直接，不会消耗多余的内存空间
思考：双重循环的时间效率低下，主要原因是会有许多重复性的操作，在此思考改进的方法，可以想象，若元素1已经得到重复次数了，后面再遇到数字1，如果再去比较明显是没有必要的，那么可以做个简单的判断，如果当前非第一个元素与上一个元素相同，就直接continue
解法2：哈希map
思路：由于可以使用双重循环遍历解决问题，那么就可以想到去利用哈希快速查找的特性来降一重循环，本质就是空间换时间，思路也很直接，直接遍历一遍数组，若当前元素存在就value加一，否则就添加该元素，比较重复最大值，返回结果。
分析：时间复杂度为n级，空间复杂度也是n级。
思考：过程就是一边查找一边添加，在查找中判断重复次数是否满足条件，能够大大提高效率。
解法3：投票法
思路：根据数组的特点，可以让数组中每个数值都拥有一票，数字相同，则票数相加，数字不同，则票数减一，当票数为0时，就换下一个人，由于数组一定存在多数值，那么一定存在票数大于0的数值，且该数值就是最大重复数
分析：时间复杂度为n级，不需要额外的内存空间，利用特点相应地去解题可以大大提高运行效率。
测试用例：
要求：数组非空，并且存在多数元素
{0} {5,8,5} {1,1,2,2,2,1,1} {2,2,3,3,3} {1,1,1} {5，4，4，4，5} {1,1,1,2,2,2,1,3,1}
代码实现
import java.util.HashMap;
/**
@author cosefy
@date 2020/6/21
*/
public class MajorityElement {
public static void main(String[] args) { //测试函数
int[] nums = {5,4,4,4,5};
int res1 = test1(nums);
int res2 = test2(nums);
int res3 = test3(nums);
System.out.print("输入数组为： ");
for (int num : nums) {
System.out.print(num + " ");
}
System.out.println();
System.out.println("测试一的结果是： " + res1);
System.out.println("测试二的结果是： " + res2);
System.out.println("测试三的结果是： " + res3);
}
//解法一:暴力解法（双重循环）
public static int test1(int[] nums) {
int maj = 0;
int max_count = 0;
for (int i = 0; i < nums.length; i++) {
if (i != 0 && nums[i] == nums[i - 1])//此处进行简单的优化，若是当前元素（非第一个）与上一个元素相同的话，就continue
continue;
int count = 1;
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] == nums[j])
++count;
}
if (max_count < count) { //判断当前元素的重复次数，是否大于原先的最大重复次数
max_count = count;
maj = nums[i];
}
}
return maj;
}
//解法二：哈希map
public static int test2(int[] nums) {
HashMap<Integer, Integer> map = new HashMap<>();
int len = nums.length;
if (len==1)
return nums[0];
for (int i = 0; i < len; i++) {
if (map.containsKey(nums[i])) {
map.put(nums[i], map.get(nums[i]) + 1);
if (map.get(nums[i]) > len / 2) //此处进行判断，可以提高时间效率
return nums[i];
} else
map.put(nums[i], 1);
}
return 0; //由于数组说明了一定存在多数元素，for循环里的return会执行，此处的return不会执行。
}
//解法三：投票法
public static int test3(int[] nums) {
if (nums.length == 1)
return nums[0];
int count = 1;
int cur = nums[0];
for (int i = 1; i < nums.length; i++) {
if (count > 0) {
if (cur == nums[i])
++count;
else
--count;
} else { //此时count为0，换下一个数字，并把count置为1
cur = nums[i];
count =1;
}
}
return cur;
}
}