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

Given [1, 1, 1, 1, 2, 2, 2], return 1

Challenge

O(n) time and O(1) extra space

.

解法

    int majorityNumber(vector nums) {
        // write your code here
        int ret, num = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (num == 0) {
                ret = nums[i];
                num++;
            } else {
                if (nums[i] == ret) {
                    num++;
                } else {
                    num--;
                }
            }
        }
        return ret;
    }

算法解釋

一個思路，同時刪除兩個不同的數，那麼結果不會變