天气冷了 ,有男朋友的抱男朋友,有女朋友的抱女朋友,而我就比较牛逼了
我不冷
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array. 题目大意是:给你一个长度为n的数组,要求你找到它的众数,众数就是在这个数组中出现次数超过n/2次数的元素,你可以假定这个数组是非空的,并且它一定会有一个满足条件的众数。 Credits: Special thanks to @ts for adding this problem and creating all test cases. #解题思路 要找众数,必然需要两个变量,一个用来保存当前候选的数字,另一个用来保存数字出现的频率,我的做法是使用一个哈希表(Hashtable)用来维护所有的数组以及它们分别出现的频率,然后在这个哈希表中寻找出现频率最大的。 代码如下:
import java.util.Hashtable;
class Solution {
public int majorityElement(int[] nums) {
Hashtable table=new Hashtable(nums.length/2);
int curr,currmax=0;
int currcount=0;
for(int i=0;i
我及其喜欢这个算法,代码简洁高效,只用了一遍遍历。不过它的核心思想我还没有参透,用这个代码一步步调试过,但是没有时间细细思考为什么这个算法可以得到正确答案,以后有时间了再来挖坟
class Solution {
public int majorityElement(int[] nums) {
int count = 0;
int major = 0;
for(int val : nums){
if(count == 0){
major = val;
count =1;
continue;
}
if(major == val) {
count++;
}
else {
count--;
}
}
return major;
}
}