FilesExpand file tree

 master

/

MajorityNumber2.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

63 lines (52 loc) · 1.43 KB

 master

/

MajorityNumber2.java

Top

File metadata and controls

• Code
• Blame

63 lines (52 loc) · 1.43 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

package Algorithms.lintcode.math;

import java.util.ArrayList;

public class MajorityNumber2 {

/**

* @param nums: A list of integers

* @return: The majority number that occurs more than 1/3

*/

public int majorityNumber(ArrayList<Integer> nums) {

// write your code

// When there are only 1 or 2 elements in the array,

// there is no solution.

if (nums == null || nums.size() <= 2) {

return -1;

}

int n1 = 0;

int n2 = 0;

int cnt1 = 0;

int cnt2 = 0;

int size = nums.size();

for (int i = 0; i < size; i++) {

int num = nums.get(i);

if (cnt1 != 0 && num == n1) {

cnt1++;

} else if (cnt2 != 0 && num == n2) {

cnt2++;

} else if (cnt1 == 0) {

cnt1 = 1;

n1 = num;

} else if (cnt2 == 0) {

cnt2 = 1;

n2 = num;

} else {

cnt1--;

cnt2--;

}

}

// count the two candiates.

cnt1 = 0;

cnt2 = 0;

for (int num: nums) {

if (num == n1) {

cnt1++;

} else if (num == n2) {

cnt2++;

}

}

if (cnt1 < cnt2) {

return n2;

}

return n1;

}

}