【大厂面试真题】系列，带你攻克大厂面试真题，秒变offer收割机！

?今日问题：给定数组找出出现次数超过数组长度一半的数

??一起看看文心快码Baidu Comate给出的答案吧！如果这个问题你也会，也可以在评论区写出你的答案哦～

@Comate

这个问题是一个经典的算法问题，通常被称为“多数元素”问题。在这个问题中，我们的目标是找到一个在数组中出现次数超过数组长度一半的数。这个问题有几种不同的解决方法，下面我会介绍两种常见的方法：

方法一：摩尔投票算法
摩尔投票算法是解决这个问题的一种高效方法，它的时间复杂度是O(n)，空间复杂度是O(1)。算法的基本思想是，由于我们要找的数字出现的次数超过了数组长度的一半，那么当我们遍历数组的时候，这个数字的出现次数会比其他所有数字出现的次数加起来还要多。因此，我们可以维护一个候选众数candidate和一个计数器count，初始时candidate可以任意选取，count为0。然后遍历数组，对于数组中的每一个元素，如果它与candidate相等，那么count加1，否则count减1。当count变为0的时候，说明我们当前维护的candidate不是众数，因此我们需要将candidate更新为当前遍历到的元素，并将count重置为1。遍历完整个数组后，candidate中存储的就是众数。

下面是一个Python实现的例子：
def majorityElement(nums):
    count = 0
    candidate = None
    for num in nums:
        if count == 0:
            candidate = num
        count += (1 if num == candidate else -1)
    return candidate
    
    方法二：哈希表
虽然摩尔投票算法是解决这个问题的高效方法，但在某些情况下，使用哈希表也是一种可行的解决方案。哈希表的时间复杂度是O(n)，但空间复杂度是O(n)。算法的基本思想是，遍历数组，并使用哈希表记录每个元素出现的次数。当我们找到一个出现次数超过数组长度一半的元素时，就可以立即返回它。

下面是一个Python实现的例子：
def majorityElement(nums):
    counts = {}
    for num in nums:
        counts[num] = counts.get(num, 0) + 1
        if counts[num] > len(nums) // 2:
            return num
注意，虽然这个方法可以解决问题，但由于它使用了额外的空间来存储哈希表，因此空间复杂度较高。在实际应用中，如果空间是一个限制因素，那么摩尔投票算法可能是更好的选择。

另外需要注意的是，题目已经明确说明了存在一个出现次数超过数组长度一半的数，所以在实际编码时不需要考虑不存在这样的数的情况。如果题目没有这样的保证，那么在使用上述方法之前，需要先进行验证。

进入文心快码 Baidu Comate 官网，体验智能编码之旅，还有超多福利！