题目：数组中有一个数字出现的次数超过数字长度的一半，请找出这个数字。例如输入一个长度为9的数组{1， 2，3， 2， 2， 2， 5， 4， 2}.由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。
解题思路：数组中有一个数字出现的次数超过数组长度的一半，它出现的次数比其他所有数字出现的次数的和还要多。我们在遍历数组的时候保存两个值：一个是数组中的一个数字，一个是次数。当遍历到下一个数字的时候，如果下一个数字和之前保存的数字相同，则次数加1；如果下一个数字和之前保存的数字不同，则次数减1。如果次数为0，保存下一个数字，并把次数设置为1。要找的数字肯定是最后一次把次数设为1时对应的数字。
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
|
private
static
bool
CheckInvalidArray(
int
[] numbers,
int
length)
{
bool
bInputInvalid =
false
;
if
(numbers ==
null
|| length <= 0)
bInputInvalid =
true
;
return
bInputInvalid;
}
private
static
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)
{
isMoreThanHalf =
false
;
}
return
isMoreThanHalf;
}
public
static
int
MoreThanHalfNum(
int
[] numbers,
int
length)
{
if
(CheckInvalidArray(numbers, length))
return
0;
int
result = numbers[0];
int
times = 1;
for
(
int
i = 1; i < length; i++)
{
if
(times == 0)
{
result = numbers[i];
times = 1;
}
else
if
(numbers[i] == result)
times++;
else
times--;
}
if
(!CheckMoreThanHalf(numbers, length, result))
result = 0;
return
result;
}
|
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
private
static
Boolean CheckInvalidArray(
int
[] numbers,
int
length) {
Boolean bInputInvalid =
false
;
if
(numbers ==
null
|| length <=
0
)
bInputInvalid =
true
;
return
bInputInvalid;
}
private
static
Boolean CheckMoreThanHalf(
int
[] numbers,
int
length,
int
number) {
int
times =
0
;
for
(
int
i =
0
; i < length; i++)
if
(numbers[i] == number)
times++;
Boolean isMoreThanHalf =
true
;
if
(times *
2
<= length) {
isMoreThanHalf =
false
;
}
return
isMoreThanHalf;
}
public
static
int
MoreThanHalfNum(
int
[] numbers,
int
length) {
if
(CheckInvalidArray(numbers, length))
return
0
;
int
result = numbers[
0
];
int
times =
1
;
for
(
int
i =
1
; i < length; i++) {
if
(times ==
0
) {
result = numbers[i];
times =
1
;
}
else
if
(numbers[i] == result)
times++;
else
times--;
}
if
(!CheckMoreThanHalf(numbers, length, result))
result =
0
;
return
result;
}
|
Python实现：
|
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
|
def
check_invalid_array(numbers, length):
b_input_invalid
=
False
if
numbers
=
=
None
or
length <
=
0
:
b_input_invalid
=
True
return
b_input_invalid
def
check_more_than_half(numbers, length, number):
times
=
0
for
item
in
numbers:
if
item
=
=
number:
times
+
=
1
is_more_than_half
=
True
if
times
*
2
<
=
length:
is_more_than_half
=
False
return
is_more_than_half
def
more_than_half_num(numbers, length):
if
check_invalid_array(numbers, length):
return
0
result
=
numbers[
0
]
times
=
1
for
item
in
numbers:
if
times
=
=
0
:
result
=
item
times
=
1
elif
item
=
=
result:
times
+
=
1
else
:
times
-
=
1
if
not
check_more_than_half(numbers, length, result):
result
=
0
return
result
|
本文转自 许大树 51CTO博客，原文链接：http://blog.51cto.com/abelxu/1978344，如需转载请自行联系原作者
