手机网站大全123456,市场监督管理局官网查询系统,小红书推广群,推广网站概况这个题非常简单#xff0c;解法有很多种#xff0c;我用的是HashMap记录每个元素出现的次数#xff0c;只要次数大于数组长度的一半就返回。下面是我的代码#xff1a;
class Solution {public int majorityElement(int[] nums) {int len nums.length/2;HashMapInteg…
这个题非常简单解法有很多种我用的是HashMap记录每个元素出现的次数只要次数大于数组长度的一半就返回。下面是我的代码
class Solution {public int majorityElement(int[] nums) {int len nums.length/2;HashMapInteger,Integer map new HashMapInteger, Integer();for(int i0;inums.length;i){int key nums[i];if(!map.containsKey(key)){map.put(key,1);if(map.get(key) len) return key;}else{map.put(key,map.get(key)1);if(map.get(key) len) return key;}}return -1;}
}
题解还有一种更牛逼的解法把数组排序然后返回数组中间的那个数就行因为如果这个数出现的次数大于数组长度的一半的话排完序后数组中间那个数一定是它。
class Solution {public int majorityElement(int[] nums) {Arrays.sort(nums);return nums[nums.length/2];}
}
还有用分治法的如果一个数是这个数组的总数那么把这个数组分成两个子数组后这个数至少是其中一个数组的众数然后选出两个众数中真正的众数即可。可以采用递归的方法不断把数组分成两个子数组直到子数组的长度为1合并左右两个数组然后再不断合并最后就可以找到整个数组的众数了
class Solution {private int countInRange(int[] nums, int num, int lo, int hi) {int count 0;for (int i lo; i hi; i) {if (nums[i] num) {count;}}return count;}private int majorityElementRec(int[] nums, int lo, int hi) {// base case; the only element in an array of size 1 is the majority// element.if (lo hi) {return nums[lo];}// recurse on left and right halves of this slice.int mid (hi - lo) / 2 lo;int left majorityElementRec(nums, lo, mid);int right majorityElementRec(nums, mid 1, hi);// if the two halves agree on the majority element, return it.if (left right) {return left;}// otherwise, count each element and return the winner.int leftCount countInRange(nums, left, lo, hi);int rightCount countInRange(nums, right, lo, hi);return leftCount rightCount ? left : right;}public int majorityElement(int[] nums) {return majorityElementRec(nums, 0, nums.length - 1);}
}
还有一种Boyer-Moore 投票算法他是先选一个候选数先把他的次数定为0如果下一个数和他一样次数加一如果不一样次数减一如果次数为0侯选数换成下一个数最后的侯选数就是众数。
class Solution {public int majorityElement(int[] nums) {int count 0;Integer candidate null;for (int num : nums) {if (count 0) {candidate num;}count (num candidate) ? 1 : -1;}return candidate;}
}
