题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

1 class Solution { 2 public: 3     int MoreThanHalfNum_Solution(vector
      
        numbers) { 4         if (numbers.size() == 0) 5             return 0; 6         int result = numbers[0]; 7         int times = 1, count = 0; 8         for (int i = 1; i < numbers.size(); i++){ 9             if (times == 0){10                 result = numbers[i];11                 times = 1;12             }13             else if (numbers[i] == result)14                 times++;15             else16                 times--;17         }18         for (int i = 1; i < numbers.size(); i++){19             if (numbers[i] == result){20                 count++;21             }22         }23         if (count >= numbers.size() / 2)24             return result;25         else26             return 0;27         28     }29 };