多数元素

1.题目描述

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：nums = [3,2,3] 输出：3 示例 2：

输入：nums = [2,2,1,1,1,2,2] 输出：2

提示： n == nums.length 1 <= n <= 5 * 10^4 -109 <= nums[i] <= 109

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

2.分析

• 暴力破解 先遍历一次得到数据中的元素，然后再遍历数组，所以复杂度是O(n^2)
• 哈希表 可以用用哈希表来快速统计每个元素出现的次数。哈希表（Hash Table）：也叫做散列表。是根据关键码值（Key Value）直接进行访问的数据结构。

哈希表通过「键 key 」和「映射函数 Hash(key) 」计算出对应的「值 value」，把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做「哈希函数（散列函数）」，存放记录的数组叫做「哈希表（散列表）」。 不同的key，不同的值 相同的key，相同的值

用哈希表来求解该问题，时间复杂度是O(n)

• 排序 先进行排序，然后再找到索引是中间的元素。 因为有排序，而最好的排序算法的时间复杂度是 O(nlogn)，所以使用排序，该算法的复杂度也是： O(nlogn)

• 分治法 如果数 a 是数组 nums 的众数，如果我们将 nums 分成两部分，那么 a 必定是至少一部分的众数。

使用经典的分治算法递归求解，直到所有的子问题都是长度为 1 的数组。长度为 1 的子数组中唯一的数显然是众数，直接返回即可。如果回溯后某区间的长度大于 1，我们必须将左右子区间的值合并。如果它们的众数相同，那么显然这一段区间的众数是它们相同的值。否则，我们需要比较两个众数在整个区间内出现的次数来决定该区间的众数。

3.代码

# 哈希
import collections
def majorityElement( nums) -> int:
    counts = collections.Counter(nums) #提供了可哈希对象的计数功能
    return max(counts.keys(), key=counts.get)

if __name__ == '__main__':
    nums = [2,2,1,1,1,2,2]
    print(majorityElement(nums))

#分治法
def majorityElement(nums) -> int:
    def majority_element_rec(lo, hi) -> int:
        # base case; the only element in an array of size 1 is the majority
        # element.
        if lo == hi:
            return nums[lo]

        # recurse on left and right halves of this slice.
        mid = (hi - lo) // 2 + lo
        left = majority_element_rec(lo, mid)
        right = majority_element_rec(mid + 1, hi)

        # if the two halves agree on the majority element, return it.
        if left == right:
            return left

        # otherwise, count each element and return the "winner".
        left_count = sum(1 for i in range(lo, hi + 1) if nums[i] == left)
        right_count = sum(1 for i in range(lo, hi + 1) if nums[i] == right)

        return left if left_count > right_count else right

    return majority_element_rec(0, len(nums) - 1)

if __name__ == '__main__':
    nums = [2,2,1,1,1,2,2]
    print(majorityElement(nums))