剑指Offer:数组中出现次数超过一半的数字

题目

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。

分析

解法一

按照老套路,看到题之后我们先从题目本身出发,努力挖掘题目的隐含条件。

由于数组中存在一个数字出现的次数超过数组长度的一半。如果将这个数组排序,那么这个数字一定会出现在数组的中间位置。这个数字就是统计学上的中位数,即长度为n的数组中第n/2大的数。这样我们就可以用快速排序中的分区思想,在O(n)时间内求得数组中任意第k大的数字,来解决这道题。

不了解快速排序的可以先在这里了解一下快速排序

和之前少有不同的是这里需要先在数组中随机选择一个数字,然后以这个数为中心来进行分区,如果选中的数字正好在中间,那这个数就是所求的结果,如果这个数小于n/2那么中位数就在右边的分区,如果这个数大于n/2那么中位数就在左边的分区,接着在相应的分区中查找即可。

需要注意的是,如果题目没有明确说明所有输入数据均合理的话,我们还需要考虑一些无效的输入。

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
// 判断无效输入
bool CheckInvalidArray(int* numbers, int length)
{
g_bInputInvalid = false;
if(numbers == nullptr && length <= 0)
g_bInputInvalid = true;

return g_bInputInvalid;
}
// 判断这个数字是否满足要求
bool CheckMoreThanHalf(int* numbers, int length, int number)
{
int times = 0;
for(int i = 0; i < length; ++i)
{
if(numbers[i] == number)
times++;
}

bool isMoreThanHalf = true;
if(times * 2 <= length)
{
g_bInputInvalid = true;
isMoreThanHalf = false;
}

return isMoreThanHalf;
}

int Partition (int[] data, int start, int end){
int index = RandomInRange(start, end);
Swap(&data[index], &data[end]);

int small = start-1;
for (index = start; index < end; index ++){
if (data[index] < data[end]){
++ small;
if (small != index){
Swap(&data[index], &data[small]);
}
}
}
++ small;
Swap(&data[small], &data[end]);
return small;
}

int MoreThanHalfNum_Solution1(int* numbers, int length)
{
if(CheckInvalidArray(numbers, length))
return 0;

int middle = length >> 1;
int start = 0;
int end = length - 1;
int index = Partition(numbers, length, start, end);
while(index != middle)
{
if(index > middle)
{
end = index - 1;
index = Partition(numbers, length, start, end);
}
else
{
start = index + 1;
index = Partition(numbers, length, start, end);
}
}

int result = numbers[middle];
if(!CheckMoreThanHalf(numbers, length, result))
result = 0;

return result;
}

解法二

接下来我们换一种思路,由于这个数出现的次数超过了数组长度的一半,也就是说它出现的次数比其它所有数字出现的次数加起来的和还要多。利用这一特性,我们可以在遍历数组的时候维护两个值:一个记录数组中的数字,一个记录次数。当我们遍历数组的时候,如果当前的数字和之前保存的数字相同,则让次数加1,否则次数减去1。当次数变为0的时候,我保存下一个数字,同时将次数设为1.继续遍历。

因为我们要找的数字出现的次数比其它数字出现的次数之和还多,这就确保了我们要找的数字肯定是最后一次把次数设置为1时对应的数字。

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
int sum = 1; // 次数
int result = array[0];
for (int i = 1; i < array.length; i ++){
if (sum == 0) {
result = array[i];
sum = 1;
}
else if (array[i] == result)
sum ++;
else
sum --;
}
int times = 0;
for (int i = 0; i < array.length; i ++){
if (array[i] == result)
times ++;
}
if (times*2 <= array.length)
return 0;
else
return result;
}
}
有收获再赞赏哦🤭
------ 本文结束感谢您的阅读-------------
0%