Majority Element
LeetCode.169. Majority Element Given an array nums of size n, return the majority element. The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.
Example:
Input: nums = [2,2,1,1,1,2,2]
Output: 2
给定一个大小为 n 的数组
nums，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。
First Solution
public static int majorityElement(int[] nums) {
int index = 0;
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.get(nums[i]) == null) {
map.put(nums[i], 1);
} else {
map.put(nums[i], map.get(nums[i]) + 1);
}
}
for (Integer integer : map.keySet()) {
if (map.get(integer) > nums.length / 2) {
index = integer;
}
}
return index;
}
遍历整个数组，对记录每个数值出现的次数(利用HashMap，其中key为数值，value为出现次数)；
接着遍历HashMap中的每个Key，寻找其value值 > nums.length / 2的key
Better Solution
public static int majorityElement(int[] nums) {
int count = 1;
int index = nums[0];
for (int i = 1; i < nums.length; i++) {
if (index == nums[i]){
count++;
}else {
count--;
if(count == 0){
index = nums[i+1];
}
}
}
return index;
}
摩尔投票法：Boyer–Moore majority vote algorithm：
从第一个数开始count=1，遇到相同的就加1，遇到不同的就减1，
减到0就重新换个数开始计数，总能找到最多的那个数字;
以下是一道关于摩尔投票法的进阶题目：
LeetCode.229.Majority Element II
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.
给定一个大小为 n 的整数数组，找出其中所有出现超过
⌊ n/3 ⌋次的元素。
Solution Version
public List<Integer> majorityElement(int[] nums) {
List<Integer> list = new ArrayList<>();
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.get(nums[i]) == null) {
map.put(nums[i], 1);
} else {
map.put(nums[i], map.get(nums[i]) + 1);
}
}
for (Integer integer : map.keySet()) {
if (map.get(integer) > nums.length / 3) {
list.add(integer);
}
}
return list;
}
原方法修改参数，返回为list即可