Majority Element
遍历一次，保存一个长度为k - 1数组：
如果数组中包括这个数，则该数count + 1
如果数组中有空位，则放入该数，count置为1
如果数组中有数字count为0，则替换该数，count置为1
所有数字count减一
最后数组中剩下的数，就是candidate，每个统计一下就可以了。
这个方法可以解决任意1 / k的majority number
Majority Element
Brute Force, O(n ^ 2) time, O(1) space
public class Solution {
public int majorityElement(int[] nums) {
int max = 0;
for (int i = 0; i < nums.length; i++) {
int num = nums[i], count = 0;
for (int j = 0; j < nums.length; j++) {
if (num == nums[j]) {
count++;
}
}
if (count * 2 > nums.length) {
return num;
}
}
return -1;
}
}
Hash Table, O(n) time, O(n) space
public class Solution {
public int majorityElement(int[] nums) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int num: nums) {
if (!map.containsKey(num)) {
map.put(num, 1);
} else {
map.put(num, map.get(num) + 1);
}
if (map.get(num) * 2 > nums.length) {
return num;
}
}
return -1;
}
}
Sort, O(nlogn) time, O(1) space
public class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length / 2];
}
}
Moore's Voting, O(n) time, O(1) space
public class Solution {
public int majorityElement(int[] nums) {
int candidate = 0, count = 0;
for (int num: nums) {
if (count == 0) {
count = 1;
candidate = num;
} else if (num == candidate) {
count++;
} else {
count--;
}
}
return candidate;
}
}
Bit, O(n) time, O(1) space
public class Solution {
public int majorityElement(int[] nums) {
int answer = 0;
for (int i = 0; i < 32; i++) {
int count = 0;
for (int num: nums) {
if ((num >> i & 1) == 1) {
count++;
}
}
if (count * 2 > nums.length) {
answer |= 1 << i;
}
}
return answer;
}
}
Majority Element II
这题的题干里没有确保一定存在major element，所以最后得出candidate以后还要再扫一遍算一下count。
public class Solution {
public List<Integer> majorityElement(int[] nums) {
int candidate1 = 0, candidate2 = 0, count1 = 0, count2 = 0;
for (int num: nums) {
if (candidate1 == num) {
count1++;
} else if (candidate2 == num) {
count2++;
} else if (count1 == 0) {
count1 = 1;
candidate1 = num;
} else if (count2 == 0) {
count2 = 1;
candidate2 = num;
} else {
count1--;
count2--;
}
}
count1 = 0;
count2 = 0;
for (int num: nums) {
if (num == candidate1) {
count1++;
} else if (num == candidate2) {
count2++;
}
}
List<Integer> result = new ArrayList<Integer>();
if (count1 * 3 > nums.length) {
result.add(candidate1);
}
if (count2 * 3 > nums.length) {
result.add(candidate2);
}
return result;
}
}
Majority Element III
如果要求element的chuxian次数是大于1/k的话，那最多会有k - 1个结果
public class Solution {
/**
* @param nums: A list of integers
* @param k: As described
* @return: The majority number
*/
public int majorityNumber(ArrayList<Integer> nums, int k) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int num: nums) {
if (map.containsKey(num)) {
map.put(num, map.get(num) + 1);
} else if (map.size() < k - 1) {
map.put(num, 1);
} else {
boolean found = false;
for (int key: map.keySet()) {
if (map.get(key) == 1) {
found = true;
map.remove(key);
map.put(num, 1);
break;
}
}
if (!found) {
for (int key: map.keySet()) {
map.put(key, map.get(key) - 1);
}
}
}
}
for (int key: map.keySet()) {
map.put(key, 0);
}
for (int num: nums) {
if (map.containsKey(num)) {
map.put(num, map.get(num) + 1);
}
}
for (int key: map.keySet()) {
if (map.get(key) * k > nums.size()) {
return key;
}
}
return -1;
}
}
(Google) Majority Element
注意这题跟之前三题的不同点是input array是排好序的。
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=191900
之前google面经里有的关于majority element的题，就是一个排序数组有n个值，求所有出现次数等于或者超过n / k的值。 比如[1 1 2 2 2 2 3 4 5 5 5 5] k = 3 return [2,5]
解决办法就是一次检查所有可能的出现majority element的位置[n / k, 2n / k, ..., n], 在每个位置上根据当前元素做search for range， O(logn), 如此重复最多k次即可。时间复杂度是O(klogn), O(1)的空间。
public class MajorityElementInSortedArray {
public static List<Integer> majorityElement(int[] array, int k) {
List<Integer> result = new ArrayList<Integer>();
List<Integer> index = new ArrayList<Integer>();
int n = array.length;
for (int i = 1; i <= k; i++) {
index.add(i * n / k - 1);
}
for (int i: index) {
int element = array[i];
int count = searchRange(array, element);
if (count * k >= n) {
result.add(element);
}
}
return result;
}
private static int searchRange(int[] array, int target) {
int start = 0, end = array.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (array[mid] >= target) {
end = mid;
} else {
start = mid;
}
}
int left = -1;
if (array[start] == target) {
left = start;
} else {
left = end;
}
start = 0;
end = array.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (array[mid] <= target) {
start = mid;
} else {
end = mid;
}
}
int right = -1;
if (array[end] == target) {
right = end;
} else {
right = start;
}
return right - left + 1;
}
public static void main(String[] args) {
int[] array = {1, 1, 2, 2, 2, 2, 3, 4, 5, 5, 5, 5};
int k = 3;
List<Integer> result = majorityElement(array, k);
System.out.println(result);
int[] array2 = {1, 2, 2, 3, 4, 4};
int k2 = 3;
List<Integer> result2 = majorityElement(array2, k2);
System.out.println(result2);
}
}