题目
给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
解法
自己的解法
思路:for循环遍历存Map,记录key对应的Count,如果大于半数,返回
package com.jzj.study.learn0527;
import java.util.HashMap;
import java.util.Map;
/**
* 给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
*/
public class LC_HalfNumber {
public static void main(String[] args) {
int[] nums = new int[9];
nums[0] = 2;
nums[1] = 2;
nums[2] = 2;
nums[3] = 3;
nums[4] = 2;
nums[5] = 4;
nums[6] = 2;
nums[7] = 21;
nums[8] = 3;
System.out.println(result(nums));
}
public static int result(int[] nums) {
Map<Integer, Integer> keyCount = new HashMap<>();
int halfLength = nums.length / 2;
for (int i = 0; i < nums.length; i++) {
int count = keyCount.getOrDefault(nums[i], 0) + 1;
if (count > halfLength) {
return nums[i];
}
keyCount.put(nums[i], count);
}
return -1;
}
}
正确解法
采用排序算法,所有元素排序完后,下标为 n/2 的一定是半数,超过了数组的一半元素长度
代码
public static int sort(int[] nums){
Arrays.sort(nums);
return nums[nums.length / 2];
}
想破头啊!这不比你HashMap 遍历快多了!