题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
题目分析
这题也有两种做法：
第一种：基于快排思想中的partition函数来做，因为根据题目，那么排序后的数组中间的数就是那个出现次数超过一半的数，那么我只需要利用快排中的partition，找到数组中间的那个数就行。
类似于之前写的查找第K大的数，只不过现在的K值为数组长度的一半
第二种：根据数组特点来做，数组中有一个数字出现的次数超过数组长度的一半，也就是说它出现的次数比其他所有数字出现的次数的和还要多，那么就可以从这里下手啦，具体看代码。
第一种要修改数组，第二种不需要修改数组。除此之外，注意检查是不是符合要求。
代码
第一种：
// 第一种
function MoreThanHalfNumSolution(numbers) {
const left = 0,
right = numbers.length - 1;
let key = partition(numbers, left, right);
const mid = numbers.length >> 1;
while (key !== mid) {
if (key > mid) {
key = partition(numbers, left, key - 1);
} else {
key = partition(numbers, key + 1, right);
}
}
let res = numbers[mid];
if (!checkMoreThanHalf(numbers, res)) {
res = 0;
}
return res;
}
function partition(a, left, right) {
const key = a[left]; // 一开始让key为第一个数
while (left < right) {
// 扫描一遍
while (key <= a[right] && left < right) {
// 如果key小于a[right]，则right递减，继续比较
right--;
}
[a[left], a[right]] = [a[right], a[left]]; // 交换
while (key >= a[left] && left < right) {
// 如果key大于a[left]，则left递增，继续比较
left++;
}
[a[left], a[right]] = [a[right], a[left]]; // 交换
}
return left; // 把key现在所在的下标返回
}
function checkMoreThanHalf(numbers, num) {
let times = 0;
for (let i = 0; i < numbers.length; i++) {
if (num === numbers[i]) {
times++;
}
}
if (times * 2 <= numbers.length) {
return false;
}
return true;
}
第二种：
// 第二种
function MoreThanHalfNumSolution2(numbers) {
let res = numbers[0],
times = 1;
for (let i = 0; i < numbers.length; i++) {
if (times === 0) {
res = numbers[i];
times = 1;
} else if (numbers[i] === res) {
times++;
} else {
times--;
}
}
if (!checkMoreThanHalf(numbers, res)) {
res = 0;
}
return res;
}
function checkMoreThanHalf2(numbers, num) {
let times = 0;
for (let i = 0; i < numbers.length; i++) {
if (num === numbers[i]) {
times++;
}
}
if (times * 2 <= numbers.length) {
return false;
}
return true;
}