Python算法-投票计数法&最小前缀和

面试题 17.10. 主要元素

数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组，找出其中的主要元素。若没有，返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。

• 方法1：哈希表

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        n = len(nums)
        hashmap = defaultdict(int)    # 初始化一个值为0的字典
        for num in nums:
            hashmap[num] += 1
            if hashmap[num] > n // 2:
                return num
        return -1

• 方法2：投票法

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count, majority = 0, -1
        for num in nums:
            # 没有票数，指定某个数位主元素
            if count == 0:
                majority = num
            # 当与主元素相同，票数增加，不相同元素相互抵消
            if num == majority:
                count += 1
            else:
                count -= 1
        if count != 0 and nums.count(majority) > len(nums) // 2:
            return majority
        else:
            return -1

2016. 增量元素之间的最大差值

给你一个下标从 0 开始的整数数组 nums ，该数组的大小为 n ，请你计算 nums[j] - nums[i] 能求得的 最大差值 ，其中 0 <= i < j < n 且 nums[i] < nums[j] 。
返回 最大差值 。如果不存在满足要求的 i 和 j ，返回 -1 。

输入：nums = [7,1,5,4]
输出：4
解释：
最大差值出现在 i = 1 且 j = 2 时，nums[j] - nums[i] = 5 - 1 = 4 。
注意，尽管 i = 1 且 j = 0 时 ，nums[j] - nums[i] = 7 - 1 = 6 > 4 ，但 i > j 不满足题面要求，所以 6 不是有效的答案。

• 方法1：暴力求解

# 暴力求解法
class Solution:
    def maximumDifference(self, nums: List[int]) -> int:
        result = []
        for i in range(len(nums)-1):
            for j in range(i+1, len(nums)):
                result.append(nums[j]-nums[i])
        if max(result) <= 0:
            return -1
        else:
            return max(result)

• 方法2：最小前缀和

class Solution:
    def maximumDifference(self, nums: List[int]) -> int:
        res = -1
        prenum = nums[0]
        n = len(nums)
        for i in range(1, n):
            if nums[i] > prenum:
                res = max(res, nums[i]-prenum)
            else:
                prenum = nums[i]
        return res
···