169、多数元素
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：[3,2,3]
输出：3
示例 2：
输入：[2,2,1,1,1,2,2]
输出：2
进阶：
尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
方法一：哈希表
1.1 思路分析
定义一个哈希表，统计每个数字出现的次数，保存在哈希表中，然后再遍历一次哈希表，找出次数大于n/2的值
1.2 代码实现
class Solution {
/**哈希表 */
public int majorityElement(int[] nums) {
Map<Integer, Integer> counts = new HashMap<Integer, Integer>();
for (int num: nums){
if (!counts.containsKey(num)){
counts.put(num, 1);
}else {
counts.put(num, counts.get(num)+1);
}
}
int len = nums.length;
int n = len / 2;
for (int key: counts.keySet()){
if (counts.get(key) > n) return key;
}
return 0;
}
}
1.3 测试结果
1.4 复杂度
- 时间复杂度：O(n)
- 空间复杂度：O(n)
方法二：先排序，找中点
2.1 思路分析
如果将数组 nums 中的所有元素按照单调递增或单调递减的顺序排序，那么下标为 ⌊ n 2 ⌋ \lfloor \dfrac{n}{2} \rfloor ⌊2n⌋的元素（下标从 0 开始）一定是众数。
如图，下划线代表众数是数组中最小的，上划线代表众数是数组中最大的，数组长度为奇数和偶数的数组众数都包含nums[n/2]这个元素。如果众数不是最值，更加会在中点重叠。
2.2 代码实现
class Solution {
/**排序+中点 */
public int majorityElement(int[] nums) {
int index = nums.length / 2;
Arrays.sort(nums); // 升序排列
return nums[index];
}
}
2.3 测试结果
2.4 复杂度
- 时间复杂度：O(nlogn)。取决于排序算法
- 空间复杂度：O(logn)。取决于排序算法
方法三：随机化
3.1 思路分析
3.2 代码实现
class Solution {
/**随机化 */
private int randRange(Random rand, int min, int max){
return rand.nextInt(max-min) + min;
}
private int countOccurences(int[] nums, int num){
int count = 0;
for (int n: nums){
if (n == num){
count++;
}
}
return count;
}
public int majorityElement(int[] nums) {
Random rand = new Random();
int majorityCount = nums.length / 2;
while(true){
int candidate = nums[randRange(rand, 0, nums.length)];
if (countOccurences(nums, candidate) > majorityCount){
return candidate;
}
}
}
}
3.3 测试结果
3.4 复杂度
方法四：分治法
4.1 思路分析
4.2 代码实现
class Solution {
/**分治 */
private int countInRange(int[] nums, int num, int low, int high){
int count = 0;
for (int i=low; i<=high; i++){
if (nums[i] == num){
count++;
}
}
return count;
}
private int majorityElementRec(int[] nums, int low, int high){
if (low == high){
return nums[low];
}
int mid = (high - low) / 2 + low;
int left = majorityElementRec(nums, low, mid);
int right = majorityElementRec(nums, mid+1, high);
if (left == right){
return left;
}
int leftCount = countInRange(nums, left, low, high);
int rightCount = countInRange(nums, right, low, high);
return leftCount > rightCount ? left : right;
}
public int majorityElement(int[] nums) {
return majorityElementRec(nums, 0, nums.length-1);
}
}
4.3 测试结果
4.4 复杂度
方法五：摩尔投票法
5.1 思路分析
该算法是指从第一个数开始count=1，遇到相同的就加1，遇到不同的就减1，即对冲消耗的思想
减到0就重新换个数开始计数，总能找到最多的那个
5.2 代码实现
class Solution {
/**投票法 */
public int majorityElement(int[] nums) {
int count = 0;
// int candidate = 0; // 可能存在零，这里换成Integer
Integer candidate = null;
for (int num: nums){
if (count == 0){
// count==0, 换数
candidate = num;
}
count += (num == candidate) ? 1: -1; // 如果相等+1，否则-1
}
return candidate;
}
}
5.3 测试结果
5.4 复杂度
- 时间复杂度：O(n)。
- 空间复杂度：O(1)。
文章评论