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.NoteThere is only one majority number in the arrayExampleFor [1, 2, 1, 2, 1, 3, 3] return 1ChallengeO(n) time and O(1) space

三三抵銷法，但是也有需要注意的地方：

1. 我們對cnt1,cnt2減數(shù)時，相當(dāng)于丟棄了3個數(shù)字（當(dāng)前數(shù)字，candidate1, candidate2）。也就是說，每一次丟棄數(shù)字，我們是丟棄3個不同的數(shù)字。

而Majority number超過了1/3所以它最后一定會留下來。

設(shè)定總數(shù)為N, majority number次數(shù)為m。丟棄的次數(shù)是x。則majority 被扔的次數(shù)是x

而m > N/3, N - 3x > 0.

3m > N, N > 3x 所以 3m > 3x, m > x 也就是說 m一定沒有被扔完

最壞的情況，Majority number每次都被扔掉了，但它一定會在n1,n2中。

2. 為什么最后要再檢查2個數(shù)字呢(從頭開始統(tǒng)計，而不用剩下的count1, count2)？因為數(shù)字的編排可以讓majority 數(shù)被過度消耗，使其計數(shù)反而小于n2，或者等于n2.前面舉的例子即是。

另一個例子：

1 1 1 1 2 3 2 3 4 4 4 這個 1就會被消耗過多，最后余下的反而比4少。

 1 public class Solution { 2     /** 3      * @param nums: A list of integers 4      * @return: The majority number that occurs more than 1/3 5      */ 6     public int majorityNumber(ArrayList<Integer> nums) { 7         // write your code 8         int candidate1 = 0; 9         int candidate2 = 0;10         int count1 = 0;11         int count2 = 0;12         for (int elem : nums) {13             if (count1 == 0) {14                 candidate1 = elem;15             }16             if (count2 == 0 && elem != candidate1) {17                 candidate2 = elem;18             }19             if (candidate1 == elem) {20                 count1++;21             }22             if (candidate2 == elem) {23                 count2++;24             }25             if (candidate1 != elem && candidate2 != elem) {26                 count1--;27                 count2--;28             }29         }30         31         count1 = 0;32         count2 = 0;33         for (int elem : nums) {34             if (elem == candidate1) count1++;35             else if (elem == candidate2) count2++;36         }37         return count1>count2? candidate1 : candidate2;38     }39 }