题目描写叙述

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

.

链接地址

http://www.lintcode.com/en/problem/majority-number/

解法

    int majorityNumber(vector<int> 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;

    }

算法解释

一个思路。同一时候删除两个不同的数。那么结果不会变