# Majority Number

Given an array of integers, the majority number is the number that occurs more than half of the size of the array. Find it.

Example

For [1, 1, 1, 1, 2, 2, 2], return 1

Challenge

O(n) time and O(1) space ## SOLUTION 1:

http://www.geeksforgeeks.org/majority-element/

1. 简单来讲，就是不断对某个议案投票，如果有人有别的议案，则将前面认为的议案的cnt减1，减到0换一个议案。

2. 投票完成后，要对majority number进行检查，以排除不存在majority number的情况。如 1，2，3，4这样的数列，是没有majory number的。

METHOD 3 (Using Moore’s Voting Algorithm)

This is a two step process.
1. Get an element occurring most of the time in the array. This phase
will make sure that if there is a majority element then it will return
that only.
2. Check if the element obtained from above step is majority element.

1. Finding a Candidate:
The algorithm for first phase that works in O(n) is known as Moore’s
Voting Algorithm. Basic idea of the algorithm is if we cancel out each
occurrence of an element e with all the other elements that are
different from e then e will exist till end if it is a majority element.

```findCandidate(a[], size)
1.  Initialize index and count of majority element
maj_index = 0, count = 1
2.  Loop for i = 1 to size – 1
(a)If a[maj_index] == a[i]
count++
(b)Else
count--;
(c)If count == 0
maj_index = i;
count = 1
3.  Return a[maj_index]
```

Above algorithm loops through each element and maintains a count of a[maj_index], If next element is same then increments the count, if next element is not same then decrements the count, and if the count reaches 0 then changes the maj_index to the current element and sets count to 1.
First Phase algorithm gives us a candidate element. In second phase we
need to check if the candidate is really a majority element. Second
phase is simple and can be easily done in O(n). We just need to check if
count of the candidate element is greater than n/2.

Example:
A[] = 2, 2, 3, 5, 2, 2, 6
Initialize:
maj_index = 0, count = 1 –> candidate ‘2?
2, 2, 3, 5, 2, 2, 6

Same as a[maj_index] => count = 2
2, 2, 3, 5, 2, 2, 6

Different from a[maj_index] => count = 1
2, 2, 3, 5, 2, 2, 6

Different from a[maj_index] => count = 0
Since count = 0, change candidate for majority element to 5 => maj_index = 3, count = 1
2, 2, 3, 5, 2, 2, 6

Different from a[maj_index] => count = 0
Since count = 0, change candidate for majority element to 2 => maj_index = 4
2, 2, 3, 5, 2, 2, 6

Same as a[maj_index] => count = 2
2, 2, 3, 5, 2, 2, 6

Different from a[maj_index] => count = 1

Finally candidate for majority element is 2.

First step uses Moore’s Voting Algorithm to get a candidate for majority element.

2. Check if the element obtained in step 1 is majority

```printMajority (a[], size)
1.  Find the candidate for majority
2.  If candidate is majority. i.e., appears more than n/2 times.
Print the candidate
3.  Else
Print "NONE"
```  ``` 1 package Algorithms.lintcode.math;
2
3 import java.util.ArrayList;
4
5 public class MajorityNumber {
6     /**
7      * @param nums: a list of integers
8      * @return: find a  majority number
9      */
10     public int majorityNumber(ArrayList<Integer> nums) {
12         if (nums == null || nums.size() == 0) {
13             // No majority number.
14             return -1;
15         }
16
17         int candidate = nums.get(0);
18
19         // The phase 1: Voting.
20         int cnt = 1;
21         for (int i = 1; i < nums.size(); i++) {
22             if (nums.get(i) == candidate) {
23                 cnt++;
24             } else {
25                 cnt--;
26                 if (cnt == 0) {
27                     candidate = nums.get(i);
28                     cnt = 1;
29                 }
30             }
31         }
32
33         // The phase 2: Examing.
34         cnt = 0;
35         for (int i = 0; i < nums.size(); i++) {
36             if (nums.get(i) == candidate) {
37                 cnt++;
38             }
39         }
40
41         // No majory number.
42         if (cnt <= nums.size() / 2) {
43             return -1;
44         }
45
46         return candidate;
47     }
48 }```

## GITHUB:

https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/lintcode/math/MajorityNumber.java

## Lintcode: Majority Number II 解题报告 Majority Number II 原题链接: http://lintcode.com/en/problem/majority-number-ii/# Given an array of integers, the majority number is the number that occurs more than 1/3 of the size of the array. Find it. Note There is only one majority number in the arra

## USACO Section1.2 Name That Number 解题报告

namenum解题报告 —— icedream61 博客园(转载请注明出处)------------------------------------------------------------------------------------------------------------------------------------------------[题目] 你有一个手机,键盘如下所示: 2: A,B,C 5: J,K,L 8: T,U,V 3: D,E,F 6: M,N,O 9:

## [LintCode] Majority Number 求众数

Given an array of integers, the majority number is the number that occurs more than half of the size of the array. Find it. Notice You may assume that the array is non-empty and the majority number always exist in the array. Have you met this questio

## Lintcode: Fast Power 解题报告 Fast Power 原题链接:http://lintcode.com/en/problem/fast-power/# Calculate the an % b where a, b and n are all 32bit integers. Example For 231 % 3 = 2 For 1001000 % 1000 = 0 Challenge O(logn) Tags Expand SOLUTION 1: 实际上这题应该是suppose n > 0的. 我们利用 取模运算的乘法法则: