forked from marsprince/SwordForOffer
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMoreThanHalfNum.java
More file actions
56 lines (54 loc) · 945 Bytes
/
MoreThanHalfNum.java
File metadata and controls
56 lines (54 loc) · 945 Bytes
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
package Problem29;
public class MoreThanHalfNum {
/*
* 数组中有一个数字出现的次数超过数组长度的一般，求这个数字
*/
public Integer moreThanHalfNum(int[] array)
{
if(array==null)
return null;
Integer number=null;
int count=0;
Integer resultInteger=null;
for(int i=0;i<array.length;i++)
{
if(number==null)
{
number=array[i];
count++;
}
else
{
if(array[i]!=number)
if(count==0)
{
number=array[i];
count=1;
}
else
count--;
else
count++;
}
if(count==1)
resultInteger=number;
}
if(checkMoreThanHalf(array, resultInteger))
return resultInteger;
else
return null;
}
private boolean checkMoreThanHalf(int[] array,int number)
{
int times=0;
for(int i=0;i<array.length;i++)
{
if(array[i]==number)
times++;
}
if(times*2<=array.length)
return false;
else
return true;
}
}