1157. 子数组中的在线多数元素

Hard

题目描述

设计一个数据结构，能够高效地找到给定子数组中的多数元素。

子数组的多数元素是指在该子数组中出现 threshold 次或更多次的元素。

实现 MajorityChecker 类：

MajorityChecker(int[] arr) 使用给定的数组 arr 初始化类的实例。
int query(int left, int right, int threshold) 返回子数组 arr[left...right] 中出现至少 threshold 次的元素，如果不存在这样的元素则返回 -1。

示例 1：

输入：
["MajorityChecker", "query", "query", "query"]
[[[1, 1, 2, 2, 1, 1]], [0, 5, 4], [0, 3, 3], [2, 3, 2]]
输出：
[null, 1, -1, 2]

解释：
MajorityChecker majorityChecker = new MajorityChecker([1, 1, 2, 2, 1, 1]);
majorityChecker.query(0, 5, 4); // 返回 1
majorityChecker.query(0, 3, 3); // 返回 -1
majorityChecker.query(2, 3, 2); // 返回 2

约束条件：

1 <= arr.length <= 2 * 10^4
1 <= arr[i] <= 2 * 10^4
0 <= left <= right < arr.length
threshold <= right - left + 1
2 * threshold > right - left + 1
最多会调用 10^4 次 query

提示：

多数元素有什么特殊性质？
多数元素出现的次数超过数组长度的一半
如果我们随机选择数组的一个索引，这个索引包含多数元素的概率是多少？
如果数组有多数元素，概率超过50%
尝试随机索引适当的次数，使得找不到答案的概率趋于零

解题思路

这道题要求设计一个数据结构来高效查询子数组中的多数元素。关键观察是题目约束条件 2 * threshold > right - left + 1，这意味着在任何查询中，最多只有一个元素能达到阈值要求。

解法一：预处理 + 二分查找 为每个元素预处理其在数组中所有出现位置的索引列表。查询时，对于子数组中可能的候选元素，使用二分查找计算其在指定范围内的出现次数。

解法二：随机化算法（推荐） 基于随机化的思想：如果一个元素在子数组中是多数元素，那么随机选择该子数组中的一个位置，选中该元素的概率超过 50%。我们可以多次随机选择位置，检查选中的元素是否满足阈值要求。

具体实现：

构造函数中，为每个元素维护其所有出现位置的索引列表
查询时，在指定范围内随机选择若干个位置（如 20 次）
对于每个随机选中的元素，使用二分查找计算其在范围内的出现次数
如果某个元素的出现次数达到阈值，立即返回；否则返回 -1

这种方法的优势是期望时间复杂度低，且实现相对简单。由于多次随机选择，找不到正确答案的概率极低。

代码实现

class MajorityChecker {
private:
    vector<int> arr;
    unordered_map<int, vector<int>> positions;
    
public:
    MajorityChecker(vector<int>& arr) : arr(arr) {
        for (int i = 0; i < arr.size(); i++) {
            positions[arr[i]].push_back(i);
        }
    }
    
    int query(int left, int right, int threshold) {
        int len = right - left + 1;
        
        // 随机选择20次
        for (int i = 0; i < 20; i++) {
            int randIdx = left + rand() % len;
            int candidate = arr[randIdx];
            
            // 使用二分查找计算候选元素在[left, right]范围内的出现次数
            auto& pos = positions[candidate];
            auto leftIt = lower_bound(pos.begin(), pos.end(), left);
            auto rightIt = upper_bound(pos.begin(), pos.end(), right);
            int count = rightIt - leftIt;
            
            if (count >= threshold) {
                return candidate;
            }
        }
        
        return -1;
    }
};

class MajorityChecker:
    def __init__(self, arr: List[int]):
        self.arr = arr
        self.positions = {}
        for i, num in enumerate(arr):
            if num not in self.positions:
                self.positions[num] = []
            self.positions[num].append(i)
    
    def query(self, left: int, right: int, threshold: int) -> int:
        import random
        import bisect
        
        length = right - left + 1
        
        # 随机选择20次
        for _ in range(20):
            rand_idx = left + random.randint(0, length - 1)
            candidate = self.arr[rand_idx]
            
            # 使用二分查找计算候选元素在[left, right]范围内的出现次数
            pos = self.positions[candidate]
            left_idx = bisect.bisect_left(pos, left)
            right_idx = bisect.bisect_right(pos, right)
            count = right_idx - left_idx
            
            if count >= threshold:
                return candidate
        
        return -1

public class MajorityChecker {
    private int[] arr;
    private Dictionary<int, List<int>> positions;
    private Random random;
    
    public MajorityChecker(int[] arr) {
        this.arr = arr;
        this.positions = new Dictionary<int, List<int>>();
        this.random = new Random();
        
        for (int i = 0; i < arr.Length; i++) {
            if (!positions.ContainsKey(arr[i])) {
                positions[arr[i]] = new List<int>();
            }
            positions[arr[i]].Add(i);
        }
    }
    
    public int Query(int left, int right, int threshold) {
        int length = right - left + 1;
        
        // 随机选择20次
        for (int i = 0; i < 20; i++) {
            int randIdx = left + random.Next(length);
            int candidate = arr[randIdx];
            
            // 使用二分查找计算候选元素在[left, right]范围内的出现次数
            var pos = positions[candidate];
            int leftIdx = BinarySearchLeft(pos, left);
            int rightIdx = BinarySearchRight(pos, right);
            int count = rightIdx - leftIdx;
            
            if (count >= threshold) {
                return candidate;
            }
        }
        
        return -1;
    }
    
    private int BinarySearchLeft(List<int> arr, int target) {
        int left = 0, right = arr.Count;
        while (left < right) {
            int mid = (left + right) / 2;
            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
    
    private int BinarySearchRight(List<int> arr, int target) {
        int left = 0, right = arr.Count;
        while (left < right) {
            int mid = (left + right) / 2;
            if (arr[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

var MajorityChecker = function(arr) {
    this.arr = arr;
    this.positions = new Map();
    
    for (let i = 0; i < arr.length; i++) {
        if (!this.positions.has(arr[i])) {
            this.positions.set(arr[i], []);
        }
        this.positions.get(arr[i]).push(i);
    }
};

MajorityChecker.prototype.query = function(left, right, threshold) {
    const length = right - left + 1;
    
    // 随机选择20次
    for (let i = 0; i < 20; i++) {
        const randIdx = left + Math.floor(Math.random() * length);
        const candidate = this.arr[randIdx];
        
        // 使用二分查找计算候选元素在[left, right]范围内的出现次数
        const pos = this.positions.get(candidate);
        const leftIdx = this.binarySearchLeft(pos, left);
        const rightIdx = this.binarySearchRight(pos, right);
        const count = rightIdx - leftIdx;
        
        if (count >= threshold) {
            return candidate;
        }
    }
    
    return -1;
};

MajorityChecker.prototype.binarySearchLeft = function(arr, target) {
    let left = 0, right = arr.length;
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
};

MajorityChecker.prototype.binarySearchRight = function(arr, target) {
    let left = 0, right = arr.length;
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

操作	时间复杂度	空间复杂度
构造函数	O(n)	O(n)
query	O(log n) 期望	O(1)

说明：

构造函数需要遍历整个数组建立位置索引，时间复杂度 O(n)，空间复杂度 O(n)
query 操作通过随机化算法，每次随机选择常数次（20次），每次使用二分查找计算出现次数，期望时间复杂度 O(log n)
由于约束条件保证最多只有一个多数元素，随机算法成功率很高，实际性能表现良好

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析