leetcode 1517 数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字（假设这个数字为k）。

O(n)做法：设置一个target，如果数组的中值等于target,则count++,否则count--，若count为0则更新这个值。

那么我们假设最差的情况，每次count为0时至少有一半的k与其他的不是k的进行抵消，那么最后一定还会存在一个k可以被标记为target。

 1 class Solution {
 2 public:
 3     int majorityElement(vector<int>& nums) {
 4       int target;
 5       int count=0;
 6       for(int i=0;i<nums.size();i++)
 7       {
 8           if(count==0)
 9           {
10               target=nums[i];
11           }
12           if(nums[i]==target)
13            count++;
14            else
15            count--;
16       }
17       return target;
18     }
19 };