Majority Number

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;
    }

算法解釋

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