题目来源: 剑指offer第 39题
方法一
数组中有一个数字出现次数超过了一半,说明这个数字的出现次数比其他所有数字的出现次数之和加起来还要多
- 在遍历数组的时候记录两个值
- 数组中的数字
- 次数
- 遍历下一个数字时,若它与之前保存的数字相同,则次数加1,否则次数减1;若次数为0,则保存下一个数字,并将次数置为1。
- 遍历结束后,所保存的数字即为所求。最后再判断它是否符合条件。
代码
class Solution {
public int moreThanHalfNum_Solution(int[] nums) {
int res = nums[0];
int count = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] == res) count++;
else count--;
if (count == 0) {
res = nums[i];
count = 1;
}
}
return res;
}
}
方法二: 基于快排的切分法
由题意可知, 所求数字是排好序数组的中位数
-
在随机快速排序算法中, 我们先在数组中随机选取一个数字,然后调整数组中的数字的顺序
-
使得比选中的数字小的数字,都排在他的左边
-
比选中的数字大的数字,都排在他的右边,
-
如果选中的数字的下标刚好是 n/2, 那么这个数字就是数组的中位数
-
如果他的下标大于 n/2, 那么中位数应该位于他的左边, 继续在他的左边部分进行查找
-
如果他的下标小于 n/2, 那么中位数应该位于他的右边, 继续在他的右边部分进行查找
-
递归进行运算
代码
class Solution {
public int moreThanHalfNum_Solution(int[] nums) {
return quickFind(nums, nums.length / 2);
}
// 快速排序方法查找
private int quickFind(int[] nums, int index) {
int l = 0;
int r = nums.length - 1;
while (l <= r) {
int p = partition(nums, l, r);
if (p < index) {
l = p + 1;
} else if (p > index) {
r = p - 1;
} else {
return nums[p];
}
}
return -1;
}
private int partition(int[] nums, int l, int r) {
int pVal = nums[l];
while (l < r) {
while (nums[r] >= pVal && l < r) r--;
nums[l] = nums[r];
while (nums[l] <= pVal && l < r) l++;
nums[r] = nums[l];
}
nums[l] = pVal;
return l;
}
}