给定一个整型数组，找出主元素，它在数组中的出现次数严格大于数组元素个数的二分之一。
注意事项
You may assume that the array is non-empty and the majority number always exist in the array.
样例
给出数组 [1,1,1,1,2,2,2] ，返回 1
挑战
要求时间复杂度为O(n)，空间复杂度为O(1)
代码
- 快速排序 O(n)
思路
一个元素出现次数大于所有元素个数的二分之一，则中间位置元素必然是这个元素
public class Solution {
/*
* @param nums: a list of integers
* @return: find a majority number
*/
public int majorityNumber(List<Integer> nums) {
if (nums == null || nums.size() == 0) {
return -1;
}
int length = nums.size() - 1;
// 注意第 k 个数，k 是从 1 开始的
return quickSelect(nums, 0, length, length / 2 + 1);
}
private int quickSelect(List<Integer> nums,
int start,
int end,
int k) {
if (start >= end) {
return nums.get(start);
}
int left = start;
int right = end;
int pivot = nums.get(left + (right - left) / 2);
while (left <= right) {
while (left <= right && nums.get(left) < pivot) {
left++;
}
while (left <= right && nums.get(right) > pivot) {
right--;
}
if (left <= right) {
int temp = nums.get(left);
nums.set(left, nums.get(right));
nums.set(right, temp);
left++;
right--;
}
}
// 此处 k - 1 即表示 k 是从 1 开始的
if (start + k - 1 <= right) {
return quickSelect(nums, start, right, k);
} else if (start + k - 1 >= left) {
return quickSelect(nums, left, end, k - left + start);
} else {
return pivot;
}
}
}
- 基于数组特点的 O(n)
思路
数组中主元素的出现次数必然大于其余所有元素出现次数，所以数组中当前元素如果与上一元素相同 count 加1，不同时 count 减1，count 为 0 时将当前元素设为主元素备选值，则遍历数组主元素备选值的最终值即为主元素的值
public class Solution {
/*
* @param nums: a list of integers
* @return: find a majority number
*/
public int majorityNumber(List<Integer> nums) {
int count = 0;
int candidate = -1;
for (int i = 0; i < nums.size(); i++) {
if (count == 0) {
count = 1;
candidate = nums.get(i);
} else if (candidate == nums.get(i)) {
count++;
} else {
count--;
}
}
return candidate;
}
}
