给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
示例 1:
输入: [3,2,3]
输出: 3
示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2
题解里说得比较通俗易懂的。https://leetcode-cn.com/problems/majority-element/solution/3chong-fang-fa-by-gfu-2/
public class MajorityElement {
/**
* 排序法
* @param nums
* @return
*/
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length/2];
}
/**
* 遍历法(哈希表)
* @param nums
* @return
*/
public int majorityElement1(int[] nums) {
int n = nums.length >> 1;
Map<Integer, Integer> map = new HashMap(nums.length);
for (int i = 0; i < nums.length; i++) {
int temp = map.get(nums[i]) == null ? 0 : map.get(nums[i]);
if (temp != 0) {
++temp;
if (temp > n) {
return nums[i];
}
map.put(nums[i], temp);
} else {
map.put(nums[i], 1);
}
}
return nums[0];
}
/**
* 摩尔投票法
* @param nums
* @return
*/
public int majorityElement2(int[] nums) {
int can_num = nums[0],count = 1;
for (int i = 1; i < nums.length; i++) {
if (can_num == nums[i]) {
++count;
} else if (--count == 0) {
can_num = nums[i];
count = 1;
}
}
return can_num;
}
public static void main(String[] args) {
// int[] nums = new int[]{1};
// int[] nums = new int[]{3,2,3};
int[] nums = new int[]{2,2,1,1,1,2,2};
MajorityElement majorityElement = new MajorityElement();
System.out.println(majorityElement.majorityElement2(nums));
}
}
Copyright: 采用 知识共享署名4.0 国际许可协议进行许可 Links: https://lixj.fun/archives/leetcode进阶之路-169多数元素