多数元素（Java版）

给定一个大小为 n 的数组 nums ，返回其中的多数元素（一个）。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：
输入：nums = [3,2,3]
输出：3
示例 2：
输入：nums = [2,2,1,1,1,2,2]
输出：2

方法一：用时1840ms

public class Solution(){
    public int majorityElement(int[] nums) {
  
        for(int i=0;i<nums.length;i++){
            int count=0;  
            //如果j=0性能会下降，也没有必要从0比起，如果i=4的话证明前四个元素并不成立，那么nums[4]=nums[0]，nums[4]也不满足条件
            for(int j=i;j<nums.length;j++){
                if(nums[i]==nums[j]){
                    count++;
                }
                if(count>nums.length/2){
                   return nums[i];
                }
            }
        }
        return -999;
    }
}   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

方法二：用时2ms

class Solution {
   public int majorityElement(int[] nums) {
   	 //进行升序排序后，中间的数字就是出现最多次数的元素
       Arrays.sort(nums); 
       return nums[nums.length / 2];
   }
}
1
2
3
4
5
6
7

方法三：用时13ms

class Solution {
    private Map<Integer, Integer> countNums(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);
            }
        }
        return counts;
    }

    public int majorityElement(int[] nums) {
        for (Map.Entry<Integer, Integer> entry : countNums(nums).entrySet()) {
            if(entry.getValue()>nums.length/2){
                return entry.getKey();
            }
        }
        return -1;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24