6927. 合法分割的最小下标 (opens new window)

1.前后缀众数

分析：可以开辟两个队列维护前后遍历的前后缀众数。然后枚举切割点，如果前半块的众数等于后半块的众数，那么返回当前切割点。

class Solution {
    public int minimumIndex(List<Integer> nums) {
        Map<Integer, Integer> map = new HashMap<>();
        List<Long> pre = new ArrayList<>();
        List<Long> post = new ArrayList<>();
        long maxval=nums.get(0),maxcount=2*Integer.MIN_VALUE;
        for (int i = 0; i < nums.size(); i++) {
            map.put(nums.get(i), map.getOrDefault(nums.get(i), 0) + 1);
            Integer count = map.get(nums.get(i));
            if(count>maxcount){
                maxval = nums.get(i);
                maxcount = count;
            }
            if(maxcount*2>i+1) pre.add(maxval);
            else pre.add((long)-1);
        }
        map.clear();
        maxval=nums.get(nums.size()-1);
        maxcount=2*Integer.MIN_VALUE;
        for (int i = nums.size()-1; i>=0; i--) {
            map.put(nums.get(i), map.getOrDefault(nums.get(i), 0) + 1);
            Integer count = map.get(nums.get(i));
            if(count>maxcount){
                maxval = nums.get(i);
                maxcount = count;
            }
            if(maxcount*2>nums.size()-i) post.add(maxval);
            else post.add((long)-1);
        }
        for(int i=0;i<nums.size()-1;i++){
            if(pre.get(i)!=-1&&post.get(nums.size()-i-2)!=-1&&pre.get(i)-post.get(nums.size()-i-2)==0) return i;
        }
        return -1;
    }
}

2.证明+枚举

结论：前一个数组的支配元素等于后一个数组的支配元素，那么这个支配元素也是整个数组的支配元素。

由于每个数组的支配元素唯一，因此实际上分割点前后的数组的支配元素已经确定了。并不需要计算前后众数是哪个，只需要求出前后数组中该元素出现的次数。如果次数满足支配元素的约束，则直接返回。