问题：假如现在有一个序列，已知其中一个数的此书超过50%，请找出这个数。比如3、3、1、1、3、2、3中，出现次数超过50%的数是3 。
方法1：两两比较，分别记录数字的出现次数，2个for循环就可以解决。时间复杂度O(N^2)。
方法2：排序后，如果这个数出现的次数大于50%的话，排序之后就应该就是位于n/2位置的那个数。
方法3：“寻找多元素问题”，我们很容易的看出来，在一个序列中如果去掉2个不同的元素，那么原序列中的出现次数超过50%的数，在新的序列中还是超过50%，因此我们只要按照序列依次扫描，先把A[0]赋值给c，增加个计数器，count = 1；然后向右扫描，如果跟c相同，则count++，不同，那么count --，这个真是我们从上面那个结论里得出的，一旦count == 0了，把c赋值为A[i+1],count = 1；，重复该过程，直到结束，这个时候，c就是那个超过50%的数。遍历一遍，时间复杂度为O(N)。
|
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
|
package
candidate;
public
class
Candidate
{
// 递归实现
public
int
candidateSort(
int
[]a,
int
start,
int
end)
{
int
c = a[start];
int
count =
1
;
int
j;
for
(j=start;j<end && count>
0
;j++)
{
if
(c == a[j])
{
count++;
}
else
{
count--;
}
}
if
(j == end)
{
return
c;
}
else
{
return
candidateSort(a, j+
1
, end);
}
}
// 循环实现
public
int
candidateSort(
int
[] a)
{
int
c = a[
0
];
int
count =
0
;
for
(
int
i=
1
; i<a.length;i++)
{
if
(c == a[i])
{
count++;
}
else
if
(count <
0
) {
c = a[i];
count =
0
;
}
else
{
count--;
}
}
return
c;
}
|
本文转自里冲51CTO博客，原文链接：http://blog.51cto.com/coollast/1887930
，如需转载请自行联系原作者
