求众数 Majority Element
题目
找出给定数组内的众数，众数含义=》在数组中出现的次数超过⌊ n/2 ⌋ 的数字。
以下为详细说明：
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.
Example 1:
Input: [3,2,3]
Output: 3
Example 2:
Input: [2,2,1,1,1,2,2]
Output: 2
思路&题解
class Solution {
public int majorityElement(int[] nums) {
int count = 1;
int maj = nums[0];
for (int i = 1; i < nums.length; i++) {
if (maj == nums[i])
count++;
else {
count--;
if (count == 0) {
maj = nums[i + 1];
}
}
}
return maj;
}
}
class Solution {
public int majorityElement(int[] nums) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(nums[i])) {
map.put(nums[i], map.get(nums[i]) + 1);
} else {
map.put(nums[i], 1);
}
}
int count = 0;
int key = 0;
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
int newValue = entry.getValue();
if (newValue > count) {
key = entry.getKey();
count = newValue;
}
}
return key;
}
}
class Solution {
public int majorityElement(int[] nums) {
for(int i = 1; i<nums.length; i++){
int j = i-1;
int key = nums[i];
while(j>=0 && nums[j]>key){
nums[j+1]=nums[j];
j--;
}
nums[j+1]=key;
}
return nums[nums.length/2];
}
}