求：数组中出现次数超过一半的数字

作者: 左家的小左 | 来源:发表于2018-07-31 15:46 被阅读0次

LeetCode 每日一题 [58] 数组中出现次数超过一半的数
39:数组中出现次数超过一半的数字
《剑指offer》— JavaScript（28）数组中出现次数
剑指offer（Java版）day07：数组中出现次数超过一半的
面试题39. 数组中出现次数超过一半的数字
JZ-028-数组中出现次数超过一半的数字
剑指offer-28-数组中出现次数超过一半的数字
29 数组中出现次数超过一半的数
剑指offer 面试题29：数组中出现次数超过一半的数字
剑指 Offer 39. 数组中出现次数超过一半的数字

题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

例如，输入一个长度为9的数组{1，2，3，2，2，2，5，4，2}。由于数字2再数组中出现了5次，超过数组长度的一半，因此输出2。

初步思路：将数组中的元素进行排序，统计每个数字出现的次数，然后找出出现次数超过一半的那个数字。这样的话排序的时间复杂度将是O(nlogn)。

在面试中，这样的时间复杂度可能不会令面试官满意，是否存在速度更快的算法呢？

解法：数组中有一个数字出现的次数超过了数组的一半等价于它出现的次数要比其他所有的数字出现的次数之和都要大。我们在遍历数组的时候保存两个值：一个是数组中的一个数字；另一个是次数。如果我们遍历的下一个数字和我们之前的数字一样，则次数+1；如果不一样，则次数-1。这样的话，我们的算法的时间效率则是O(n)。