Majority Number I （找一个出现次数>1/2的数）
Given an array of integers, the majority number is the number that occurs more than half of the size of the array. Find it.
Example
Given [1, 1, 1, 1, 2, 2, 2], return 1
Challenge
O(n) time and O(1) extra space
Solution: 用的抵消的思想，如果两个数不一样大，就相互抵消，一样大就保留， 用count计数
public int majorityNumber(ArrayList<Integer> nums) {
int candidate = -1;
int count = 0;
for (int i = 0; i < nums.size(); i++) {
if (count == 0) {
candidate = nums.get(i);
count++;
} else {
if (candidate == nums.get(i)) {
count++;
} else {
count--;
}
}
}
return candidate;
}
Majority Number II （找一个出现次数>1/3的数）
Given an array of integers, the majority number is the number that occurs more than 1/3 of the size of the array.
Find it.
Example
Given [1, 2, 1, 2, 1, 3, 3], return 1.
There is only one majority number in the array.
O(n) time and O(1) extra space.
Solution: 策略和I一样，只是现在有两个candidate,
public int majorityNumber(ArrayList<Integer> nums) {
int candidate1 = -1;
int candidate2 = -1;
int count1 = 0;
int count2 = 0;
for (Integer num : nums) {
if (candidate1 == num) {
count1 ++;
} else if (candidate2 == num) {
count2 ++;
} else if (count1 == 0) {
candidate1 = num;
count1 = 1;
} else if (count2 == 0) {
candidate2 = num;
count2 = 1;
} else {
count1--;
count2--;
}
}
if (count1 == 0) {
return candidate2;
}
if (count2 == 0) {
return candidate1;
}
count1 = 0;
count2 = 0;
for (Integer num : nums) {
if (num == candidate1) {
count1++;
}
if (num == candidate2) {
count2++;
}
}
return count1 > count2 ? candidate1 : candidate2;
}
Majority Number III （找一个出现次数>1/k的数）
Given an array of integers and a number k, the majority number is the number that occurs more than 1/k of the size of the array.
Find it.
Example
Given [3,1,2,3,2,3,3,4,4,4] and k=3, return 3.
There is only one majority number in the array.
O(n) time and O(k) extra space
Solution: Similar approach as I & II
public int majorityNumber(ArrayList<Integer> nums, int k) {
Map<Integer, Integer> majorityCounts = new HashMap<>();
for (Integer num : nums) {
if (majorityCounts.containsKey(num)) {
majorityCounts.put(num, majorityCounts.get(num) + 1);
} else {
if (majorityCounts.size() < k - 1) {
majorityCounts.put(num, 1);
} else {
List<Integer> toBeRemoved = new ArrayList<>();
for (Integer key : majorityCounts.keySet()) {
if (majorityCounts.get(key) > 1) {
majorityCounts.put(key, majorityCounts.get(key) - 1);
} else {
toBeRemoved.add(key);
}
}
//important here: can not remove the element while iterating the set
//which will cause ConcurrentModificationException
for (Integer key : toBeRemoved) {
majorityCounts.remove(key);
}
}
}
}
Set<Integer> results = majorityCounts.keySet();
int maxCount = 0;
int candidate = 0;
for (Integer key : majorityCounts.keySet()) {
majorityCounts.put(key, 0);
}
for (Integer num : nums) {
if (majorityCounts.containsKey(num)) {
int count = majorityCounts.get(num) + 1;
majorityCounts.put(num, count);
if (count > maxCount) {
maxCount = count;
candidate = num;
}
}
}
return candidate;
}
