合法分割的最小下标

标签: 数组 哈希表 排序

难度: Medium

如果元素 x 在长度为 m 的整数数组 arr 中满足 freq(x) * 2 > m ，那么我们称 x 是 支配元素 。其中 freq(x) 是 x 在数组 arr 中出现的次数。注意，根据这个定义，数组 arr 最多 只会有 一个 支配元素。

给你一个下标从 0 开始长度为 n 的整数数组 nums ，数据保证它含有一个支配元素。

你需要在下标 i 处将 nums 分割成两个数组 nums[0, ..., i] 和 nums[i + 1, ..., n - 1] ，如果一个分割满足以下条件，我们称它是 合法 的：

  • 0 <= i < n - 1
  • nums[0, ..., i] 和 nums[i + 1, ..., n - 1] 的支配元素相同。

这里， nums[i, ..., j] 表示 nums 的一个子数组，它开始于下标 i ，结束于下标 j ，两个端点都包含在子数组内。特别地，如果 j < i ，那么 nums[i, ..., j] 表示一个空数组。

请你返回一个 合法分割 的 最小 下标。如果合法分割不存在，返回 -1 。

示例 1：

输入：nums = [1,2,2,2]
输出：2
解释：我们将数组在下标 2 处分割，得到 [1,2,2] 和 [2] 。
数组 [1,2,2] 中，元素 2 是支配元素，因为它在数组中出现了 2 次，且 2 * 2 > 3 。
数组 [2] 中，元素 2 是支配元素，因为它在数组中出现了 1 次，且 1 * 2 > 1 。
两个数组 [1,2,2] 和 [2] 都有与 nums 一样的支配元素，所以这是一个合法分割。
下标 2 是合法分割中的最小下标。

示例 2：

输入：nums = [2,1,3,1,1,1,7,1,2,1]
输出：4
解释：我们将数组在下标 4 处分割，得到 [2,1,3,1,1] 和 [1,7,1,2,1] 。
数组 [2,1,3,1,1] 中，元素 1 是支配元素，因为它在数组中出现了 3 次，且 3 * 2 > 5 。
数组 [1,7,1,2,1] 中，元素 1 是支配元素，因为它在数组中出现了 3 次，且 3 * 2 > 5 。
两个数组 [2,1,3,1,1] 和 [1,7,1,2,1] 都有与 nums 一样的支配元素，所以这是一个合法分割。
下标 4 是所有合法分割中的最小下标。

示例 3：

输入：nums = [3,3,3,3,7,2,2]
输出：-1
解释：没有合法分割。

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • nums 有且只有一个支配元素。

Submission

运行时间: 83 ms

内存: 30.7 MB

class Solution:
    def minimumIndex(self, nums: List[int]) -> int:
        # 贪心加校验
        # 先获取支配元素
        c = Counter(nums)
        fr = 0
        cnt = 0
        for u, v in c.items():
            if v > cnt:
                cnt = v
                fr = u
        
        # 开始找最小分割点
        freq = 0
        bk = 0
        for i, x in enumerate(nums):
            if x == fr:
                freq += 1
                if freq * 2 > (i+1):
                    bk = i
                    break
        
        return bk if (cnt - freq) * 2 > (len(nums) - bk - 1) else -1

Explain

本题解使用了贪心加校验的方法。首先，通过统计数组中每个元素的频率，找到支配元素（频率最高且满足支配条件的元素）。接着，从数组的起点开始，逐个元素累加支配元素的出现次数，寻找最小的符合条件的下标i，使得在该下标处分割数组后，左侧子数组的支配元素仍然是整体的支配元素。最后，验证右侧子数组是否满足支配元素的条件。如果都满足，则返回该下标；如果找不到符合条件的下标，则返回-1。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def minimumIndex(self, nums: List[int]) -> int:
        # 使用Counter统计各元素频率
        c = Counter(nums)
        fr = 0
        cnt = 0
        # 找到支配元素fr
        for u, v in c.items():
            if v > cnt:
                cnt = v
                fr = u
        
        # 寻找最小合法分割点
        freq = 0
        bk = 0
        for i, x in enumerate(nums):
            if x == fr:
                freq += 1
                # 检查当前部分是否支配
                if freq * 2 > (i+1):
                    bk = i
                    break
        
        # 验证右侧数组是否以fr为支配元素
        return bk if (cnt - freq) * 2 > (len(nums) - bk - 1) else -1

Explore

题解中并没有明确确保数组中只存在一个支配元素，而是通过统计各元素的频率，并选取频率最高的元素作为支配元素。如果存在多个元素具有相同的最高频率，则题解中的方法会选取最后一个满足条件的元素作为支配元素。这并不严格确保只有一个支配元素，只是确保了选取的支配元素在原数组中出现次数最多。

是的，题解中使用了Python的Counter类来统计频率，并通过遍历Counter的结果来更新找到的频率最高的元素。当多个元素频率相同时，题解中的方法确实只选择了在遍历中最后遇到的满足条件的元素作为支配元素。这可能不是最优的选择，特别是如果考虑支配元素的选取对问题解决的影响。

题解中的贪心方法主要是通过检查在某个下标处分割后，左侧子数组中的支配元素是否仍然满足支配条件。然而，对于右侧数组，题解仅仅检查了剩余的支配元素频率是否足以让它在右侧仍为支配元素，但没有考虑到其他元素的频率可能在右侧子数组中增加，这可能导致新的支配元素的出现。因此，虽然题解考虑了部分问题，但没有完全确保右侧子数组中不会出现新的支配元素。

题解中的方法在找到第一个满足左侧子数组支配元素条件的下标后即结束循环，这是基于贪心策略的决定。贪心策略的目标是尽可能早地找到一个解决方案，并不保证找到的是最优解。此外，一旦找到一个符合条件的分割点，就意味着左侧部分已符合条件，继续寻找其他分割点可能会破坏这一条件，因此在找到第一个符合条件的分割点后停止搜索是合理的。