169. Majority Element

https://leetcode.com/problems/majority-element/

给定一个数组，其长度为n,其中存在一个数，它出现的次数超过了n/2次，求出这个数

分析

从数组中同时减去两个不同的数，可以看到后面剩下的数组中，出现次数最多的数字仍然超过了 一半；
因此可以先从数组中取一个数放到模板中，然后再拿下一个数字和模板比较，如果相同，那么模板出现的次数加1，如果不相同，把这个数字和模板数字都删掉，（删掉对于模板数字来说就是出现的次数减1），然后最后面存在的模板数字就是那个次数出现超过一半的数字；

通俗的来讲就是两个军队打仗，假设一对一双方都会伤亡，那么最后胜利留下的肯定是人多的

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int ntime=0;
        int temp=0;
        for(int i=0; i<nums.size(); ++i)
        {
            if(ntime==0)
            {
                temp=nums[i];
                ntime=1;
            }
            else if(temp==nums[i])
                ntime ++;
            else
                ntime --;
        }
        return temp;
    }
};

结果：

Runtime: 16 ms, faster than 96.31% of C++ online submissions for Majority Element.
Memory Usage: 9 MB, less than 100.00% of C++ online submissions for Majority Element.