Question

2780. 合法分割的最小下标

English Version

题目描述

如果元素 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 有且只有一个支配元素。

解法

方法一：哈希表

我们用哈希表统计每个元素出现的次数，然后找出出现次数最多的元素 $x$，即为支配元素。要使得分割后的两个数组中都有支配元素，且支配元素相同，那么支配元素一定是 $x$。

接下来，我们只需要遍历数组 $nums$，累加前缀中 $x$ 的出现次数 $cur$，并判断 $x$ 在后缀中出现的次数是否满足要求即可。如果满足要求，那么当前下标 $i$ 就是一个可行的分割下标，我们只需要选择所有可行分割下标中最小的那个即可。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是数组 $nums$ 的长度。

class Solution:
  def minimumIndex(self, nums: List[int]) -> int:
    x, cnt = Counter(nums).most_common(1)[0]
    cur = 0
    for i, v in enumerate(nums, 1):
      if v == x:
        cur += 1
        if cur * 2 > i and (cnt - cur) * 2 > len(nums) - i:
          return i - 1
    return -1

class Solution {
  public int minimumIndex(List<Integer> nums) {
    int x = 0, cnt = 0;
    Map<Integer, Integer> freq = new HashMap<>();
    for (int v : nums) {
      int t = freq.merge(v, 1, Integer::sum);
      if (cnt < t) {
        cnt = t;
        x = v;
      }
    }
    int cur = 0;
    for (int i = 1; i <= nums.size(); ++i) {
      if (nums.get(i - 1) == x) {
        ++cur;
        if (cur * 2 > i && (cnt - cur) * 2 > nums.size() - i) {
          return i - 1;
        }
      }
    }
    return -1;
  }
}

class Solution {
public:
  int minimumIndex(vector<int>& nums) {
    int x = 0, cnt = 0;
    unordered_map<int, int> freq;
    for (int v : nums) {
      ++freq[v];
      if (freq[v] > cnt) {
        cnt = freq[v];
        x = v;
      }
    }
    int cur = 0;
    for (int i = 1; i <= nums.size(); ++i) {
      if (nums[i - 1] == x) {
        ++cur;
        if (cur * 2 > i && (cnt - cur) * 2 > nums.size() - i) {
          return i - 1;
        }
      }
    }
    return -1;
  }
};

func minimumIndex(nums []int) int {
  x, cnt := 0, 0
  freq := map[int]int{}
  for _, v := range nums {
    freq[v]++
    if freq[v] > cnt {
      x, cnt = v, freq[v]
    }
  }
  cur := 0
  for i, v := range nums {
    i++
    if v == x {
      cur++
      if cur*2 > i && (cnt-cur)*2 > len(nums)-i {
        return i - 1
      }
    }
  }
  return -1
}

function minimumIndex(nums: number[]): number {
  let [x, cnt] = [0, 0];
  const freq: Map<number, number> = new Map();
  for (const v of nums) {
    freq.set(v, (freq.get(v) ?? 0) + 1);
    if (freq.get(v)! > cnt) {
      [x, cnt] = [v, freq.get(v)!];
    }
  }
  let cur = 0;
  for (let i = 1; i <= nums.length; ++i) {
    if (nums[i - 1] === x) {
      ++cur;
      if (cur * 2 > i && (cnt - cur) * 2 > nums.length - i) {
        return i - 1;
      }
    }
  }
  return -1;
}