题目链接：https://leetcode.cn/problems/threshold-majority-queries/description/

题目3636

解题思路

  1. 问题分析：对于每个查询，需要在子数组 nums[l..r] 中找到出现次数至少为 threshold 次的元素，再从这些元素里选频率最高的（频率相同选值最小的），若没有符合条件的元素则返回 -1 。由于数据规模较大（nums 长度可达 (10^5) ，queries 数量可达 (5×10^4) ），直接对每个查询遍历子数组统计频率会超时，需要更高效的方法。
  2. 预处理与数据结构选择：
    • 频率统计：可以利用哈希表（如 HashMap ）来统计子数组中元素的频率，但直接每次查询都统计仍效率低。考虑到题目中 threshold 的约束（1 <= threshold <= r_i - l_i + 1 ），可结合摩尔投票法的思想，或者通过预处理不同区间的频率信息。不过更实际的是，针对每个查询，先确定子数组范围，然后高效统计其中元素频率。
    • 优化思路：可以借助前缀和数组的思想，针对每个元素，预处理其在数组中每个位置之前的出现次数，这样在查询子数组时，能快速计算出该元素在子数组中的出现次数。但元素值范围较大（1 <= nums[i] <= 10^9 ），无法为每个元素都建立前缀和数组。所以换个思路，对于每个查询，遍历子数组统计频率时，利用哈希表记录元素出现次数，同时筛选出出现次数满足 threshold 的元素，再在这些元素里找符合要求的结果。
  3. 具体步骤：
    • 遍历每个查询 queries[i] ，提取 l、r、threshold 。
    • 针对子数组 nums[l..r] ，使用 HashMap<Integer, Integer> 统计每个元素的出现次数。
    • 遍历哈希表，筛选出出现次数 >= threshold 的元素，存入一个临时列表。
    • 如果临时列表为空，当前查询结果为 -1 ；否则，遍历临时列表，找出频率最高的元素（频率相同选值最小的 ）。

Java 代码实现


import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution {
    /**
     * 解决问题的主方法
     * @param nums 输入的整数数组
     * @param queries 查询数组，每个查询包含三个元素: l(左索引), r(右索引), threshold(阈值)
     * @return 每个查询对应的结果数组
     */
    public int[] solve(int[] nums, int[][] queries) {
        // 结果数组，长度与查询数量相同
        int[] ans = new int[queries.length];
        
        // 遍历每个查询
        for (int i = 0; i < queries.length; i++) {
            // 提取当前查询的参数：左索引、右索引和阈值
            int l = queries[i][0];
            int r = queries[i][1];
            int threshold = queries[i][2];
            
            // 用于统计子数组nums[l..r]中每个元素的出现频率
            Map<Integer, Integer> freqMap = new HashMap<>();
            
            // 遍历子数组，统计每个元素的出现次数
            for (int j = l; j <= r; j++) {
                // 从map中获取当前元素的计数，默认为0，然后加1
                freqMap.put(nums[j], freqMap.getOrDefault(nums[j], 0) + 1);
            }
            
            // 存储所有出现次数不少于threshold的元素（候选元素）
            List<Integer> candidates = new ArrayList<>();
            
            // 遍历频率映射，筛选出符合条件的候选元素
            for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
                // 如果元素出现次数 >= threshold，则加入候选列表
                if (entry.getValue() >= threshold) {
                    candidates.add(entry.getKey());
                }
            }
            
            // 处理候选元素，确定当前查询的结果
            if (candidates.isEmpty()) {
                // 没有符合条件的元素，结果为-1
                ans[i] = -1;
            } else {
                // 初始化结果为候选列表中的第一个元素
                int res = candidates.get(0);
                // 初始化最大频率为该元素的频率
                int maxFreq = freqMap.get(res);
                
                // 遍历所有候选元素，找到最佳结果
                for (int num : candidates) {
                    int freq = freqMap.get(num);
                    // 条件1：频率更高的元素更优
                    // 条件2：频率相同的情况下，数值更小的元素更优
                    if (freq > maxFreq || (freq == maxFreq && num < res)) {
                        res = num;
                        maxFreq = freq;
                    }
                }
                
                // 将找到的最佳结果存入结果数组
                ans[i] = res;
            }
        }
        
        // 返回所有查询的结果
        return ans;
    }
}

代码说明

  • 外层循环：遍历每个查询，依次处理。
  • 哈希表统计频率：通过内层循环遍历子数组 nums[l..r] ，用 HashMap 统计每个元素出现次数。
  • 筛选候选元素：遍历哈希表，把出现次数满足 threshold 的元素加入候选列表。
  • 确定结果元素：遍历候选列表，按照频率最高（同频率选值小 ）的规则找出结果，存入 ans 数组对应位置。 该方法思路直接，但对于极端大数据量（如 nums 长度 (10^5) 且 queries 数量 (5×10^4) ），时间复杂度较高（每个查询遍历子数组的时间是 (O(r - l + 1)) ，最坏总时间复杂度接近 (O(5×10^9)) ），实际可能需要更优化的算法（如分块处理、莫队算法等 ）来降低时间复杂度，不过上述代码能正确解决问题，适合理解基本思路。