class Solution {
public:
int minimumIndex(vector<int>& nums) {
}
};
6927. 合法分割的最小下标
如果元素 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 - 1nums[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 <= 1051 <= nums[i] <= 109nums 有且只有一个支配元素。原站题解
java 解法, 执行用时: 31 ms, 内存消耗: 57.8 MB, 提交时间: 2023-07-17 11:05:52
class Solution {
public int minimumIndex(List<Integer> nums) {
HashMap<Integer, Integer> map = new HashMap<>();
int target = 0, target_num = 0;
for(int x: nums){
int a = map.getOrDefault(x, 0) + 1;
map.put(x, a);
if(a * 2 > nums.size()){
target = x;
target_num = a;
}
}
int cnt = 0;
for(int i = 0; i < nums.size(); i++){
if(nums.get(i) == target) cnt++;
if(cnt * 2 > i + 1 && (target_num - cnt) * 2 > nums.size() - i - 1)
return i;
}
return -1;
}
}
cpp 解法, 执行用时: 224 ms, 内存消耗: 91.6 MB, 提交时间: 2023-07-17 11:05:38
class Solution {
public:
int minimumIndex(vector<int>& nums) {
unordered_map<int, int> cnt;
for(int x : nums) ++cnt[x];
auto [x, c] = *max_element(cnt.begin(), cnt.end(),
[](auto a, auto b) { return a.second < b.second; });
int n = nums.size();
if(c * 2 <= n) return -1;
int c1 = 0, c2;
for(int i = 0; i < n - 1; ++i) {
c1 += nums[i] == x, c2 = c - c1;
if(c1 * 2 > i + 1 && c2 * 2 > n - i - 1) return i;
}
return -1;
}
};
golang 解法, 执行用时: 120 ms, 内存消耗: 10.6 MB, 提交时间: 2023-07-17 11:00:10
func minimumIndex(nums []int) int {
// 也可以用摩尔投票法实现
freq := map[int]int{}
mode := nums[0]
for _, x := range nums {
freq[x]++
if freq[x] > freq[mode] {
mode = x
}
}
total := freq[mode]
freq1 := 0
for i, x := range nums {
if x == mode {
freq1++
}
if freq1*2 > i+1 && (total-freq1)*2 > len(nums)-i-1 {
return i
}
}
return -1
}
python3 解法, 执行用时: 168 ms, 内存消耗: 32.6 MB, 提交时间: 2023-07-17 10:59:56
# 分割出的两个数组的支配元素就是原数组的支配元素。
class Solution:
def minimumIndex(self, nums: List[int]) -> int:
mode, total = Counter(nums).most_common(1)[0]
freq1 = 0
for i, x in enumerate(nums):
freq1 += x == mode
if freq1 * 2 > i + 1 and (total - freq1) * 2 > len(nums) - i - 1:
return i
return -1