leetcode 169. Majority Element
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:
Output: 3
Example 2:
Input:
Output: 2
class Solution {
public int majorityElement(int[] nums) {
if (nums.length == 0) return 0;
if (nums.length == 1) return nums;
Map<Integer, Integer> map = new HashMap<>();
for(int i : nums) {
map.put(i, map.getOrDefault(i,0)+1);
if(map.get(i) > (nums.length/2)){
return i;
}
}
return -1;
}
}
bucket sort!!
class Solution {
public int majorityElement(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for(int i : nums) map.put(i, map.getOrDefault(i,0)+1);
List<Integer>[] bucket = new List;
for(Integer i : map.keySet()){
int fre = map.get(i);
if(bucket == null) bucket = new ArrayList<>();
bucket.add(i);
}
List<Integer> list =new ArrayList<>();
for(int i = bucket.length -1 ; i >= 0 && list.size()<=1; i--)
if(bucket != null)
list.addAll(bucket);
return list.get(0);
}
}
class Solution {
public int majorityElement(int[] nums) {
if(nums.length == 0) return 0;
if(nums.length == 1) return nums;
int res = nums;
int fre = 1;
for(int i = 1; i < nums.length; i++){
if(nums == res) fre ++;
else fre --;
if(fre == 0) {
res = nums;
fre = 1;
}
}
return res;
}
}
页:
[1]