腾讯二面：多数元素
前言:
以前做数学题的时候，老师说：你们学习多种解题方法。遇到类似不同的问题，你都会了，这样能提高解题能力。如果你写出多种解法，面试官会对你刮目相看。
下面一题，我们将用多种解法实现，是面试中常见的一题。
题目：
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指，在数组中出现次数，大于 n / 2 的元素。
例子：int a[3] = {1, 2, 2} ，多数元素是 2 。
你可以假设数组是非空的，并且给定的数组中，总是存在多数元素。
解法一：哈希表
动画演示：
代码如下：
哈希表方法：一边遍历，一边计数，一边找众数，并不是先计数完，再去遍历一次找最大值。
时间复杂度：O(n) ；空间复杂度：O(n)
解法二：排序
代码如下：
时间复杂度：O(nlogn)；空间复杂度：O(nlogn)
解法三：分治
动画演示：
代码如下：
先将数组划分，然后分别找到左边的众数和右边的众数，然后根据找到的众数和数组长度的 1 / 2 进行比较。
时间复杂度：O(nlogn) ；空间复杂度：O(nlogn)
解法4：Boyer- Moore算法
思想：我们把众数记为 +1，把其他数记为 -1，将它们全部加起来，显然和大于 0。从结果本身，我们可以看出，众数比其他数多。
代码如下：
如果 x 与 more相等，那么计数器 count 的值增加 1；
如果 x 与 more不等，那么计数器 count 的值减少 1。
时间复杂度：O(n)；空间复杂度：O(1)
絮叨
面试过程中，选择你熟悉的算法中，时间和空间复杂度最优的解法，平时训练多种方法都要懂，提高算法能力。
评论