阅读视图

欢迎关注 B站@灵茶山艾府

动态规划 + 二分查找优化（Python/Java/C++/Go/JS/Rust）

endlesscheng

2022年10月22日 07:35

请先完成本题的简单版本：1235. 规划兼职工作，我的题解。

注意 1235 题两个相邻区间的端点可以相同，本题不能相同。

本题在 1235 的基础上，约束参加的会议个数至多为 $k$。相应地，DP 要增加一个参数 $j$，表示至多参加 $j$ 个会议。

和 1235 一样，按照结束时间排序。定义 $f[i+1][j]$ 表示参加 $\textit{events}[0]$ 到 $\textit{events}[i]$ 中的至多 $j$ 个会议，能得到的最大价值和。其中 $+1$ 是为了方便用 $f[0]$ 表示初始值，即没有会议的情况。

分类讨论：

不参加 $\textit{events}[i]$，问题变成参加 $\textit{events}[0]$ 到 $\textit{events}[i-1]$ 中的至多 $j$ 个会议，能得到的最大价值和，即 $f[i][j]$；
参加 $\textit{events}[i]$，设 $p$ 是最大的满足 $\textit{endDay}_p<\textit{startDay}_i$ 的 $p$（若不存在则 $p=-1$），问题变成参加 $\textit{events}[0]$ 到 $\textit{events}[p]$ 中的至多 $j-1$ 个会议，能得到的会议价值的最大和，即 $f[p+1][j-1] + \textit{value}_i$。

两种情况取最大值，得到状态转移方程：

$$
f[i+1][j] = \max(f[i][j], f[p+1][j-1] + \textit{value}_i)
$$

由于结束时间是有序的（我们排过序了），$p$ 可以用二分查找快速计算，原理见二分查找红蓝染色法【基础算法精讲 04】。

初始值：$f[0][j] = 0$。没有会议，价值和为 $0$。

答案：$f[n][k]$。

优化：如果 $k=1$，只能参加一个会议，直接返回最大的价值。

# 手写 max 更快
fmax = lambda a, b: b if b > a else a

class Solution:
    def maxValue(self, events: List[List[int]], k: int) -> int:
        # 特判 k=1 的情况可以更快
        if k == 1:
            return max(e[2] for e in events)

        events.sort(key=lambda e: e[1])  # 按照结束时间排序
        n = len(events)
        f = [[0] * (k + 1) for _ in range(n + 1)]
        for i, (start_day, _, value) in enumerate(events):
            p = bisect_left(events, start_day, hi=i, key=lambda e: e[1])  # hi=i 表示二分上界为 i（默认为 n）
            for j in range(1, k + 1):
                # 为什么是 p 不是 p+1：上面算的是 >= start_day，-1 后得到 < start_day，但由于还要 +1，抵消了
                f[i + 1][j] = fmax(f[i][j], f[p][j - 1] + value)
        return f[n][k]

class Solution {
    public int maxValue(int[][] events, int k) {
        // 特判 k=1 的情况可以更快
        if (k == 1) {
            int mx = 0;
            for (int[] e : events) {
                mx = Math.max(mx, e[2]);
            }
            return mx;
        }

        Arrays.sort(events, (a, b) -> a[1] - b[1]); // 按照结束时间排序
        int n = events.length;
        int[][] f = new int[n + 1][k + 1];
        for (int i = 0; i < n; i++) {
            int p = search(events, i, events[i][0]);
            for (int j = 1; j <= k; j++) {
                f[i + 1][j] = Math.max(f[i][j], f[p + 1][j - 1] + events[i][2]);
            }
        }
        return f[n][k];
    }

    // 返回 endDay[i] < upper 的最大 i
    private int search(int[][] events, int right, int upper) {
        int left = -1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (events[mid][1] < upper) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

class Solution {
public:
    int maxValue(vector<vector<int>>& events, int k) {
        // 特判 k=1 的情况可以更快
        if (k == 1) {
            return ranges::max(events, {}, [](auto& e) { return e[2]; })[2];
        }

        ranges::sort(events, {}, [](auto& e) { return e[1]; }); // 按照结束时间排序
        int n = events.size();
        vector f(n + 1, vector<int>(k + 1));
        for (int i = 0; i < n; i++) {
            int p = lower_bound(events.begin(), events.begin() + i, events[i][0],
                                [](auto& e, int lower) { return e[1] < lower; }) - events.begin();
            for (int j = 1; j <= k; j++) {
                // 为什么是 p 不是 p+1：上面算的是 >= startDay，-1 后得到 < startDay，但由于还要 +1，抵消了
                f[i + 1][j] = max(f[i][j], f[p][j - 1] + events[i][2]);
            }
        }
        return f[n][k];
    }
};

func maxValue(events [][]int, k int) int {
    // 特判 k=1 的情况可以更快
    if k == 1 {
        mx := 0
        for _, e := range events {
            mx = max(mx, e[2])
        }
        return mx
    }

    slices.SortFunc(events, func(a, b []int) int { return a[1] - b[1] })
    n := len(events)
    f := make([][]int, n+1)
    for i := range f {
        f[i] = make([]int, k+1)
    }
    for i, e := range events {
        startDay, value := e[0], e[2]
        p := sort.Search(i, func(j int) bool { return events[j][1] >= startDay })
        for j := 1; j <= k; j++ {
            // 为什么是 p 不是 p+1：上面算的是 >= startDay，-1 后得到 < startDay，但由于还要 +1，抵消了
            f[i+1][j] = max(f[i][j], f[p][j-1]+value)
        }
    }
    return f[n][k]
}

var maxValue = function(events, k) {
    // 特判 k=1 的情况可以更快
    if (k === 1) {
        return _.maxBy(events, e => e[2])[2];
    }

    events.sort((a, b) => a[1] - b[1]);
    const n = events.length;
    const f = Array.from({ length: n + 1 }, () => Array(k + 1).fill(0));
    for (let i = 0; i < n; i++) {
        const p = search(events, i, events[i][0]);
        for (let j = 1; j <= k; j++) {
            f[i + 1][j] = Math.max(f[i][j], f[p + 1][j - 1] + events[i][2]);
        }
    }
    return f[n][k];
};

// 返回 endDay[i] < upper 的最大 i
var search = function(events, right, upper) {
    let left = -1;
    while (left + 1 < right) {
        const mid = (left + right) >>> 1;
        if (events[mid][1] < upper) {
            left = mid;
        } else {
            right = mid;
        }
    }
    return left;
};

impl Solution {
    pub fn max_value(mut events: Vec<Vec<i32>>, k: i32) -> i32 {
        // 特判 k=1 的情况可以更快
        if k == 1 {
            return events.into_iter().map(|e| e[2]).max().unwrap();
        }

        events.sort_unstable_by_key(|a| a[1]);
        let n = events.len();
        let k = k as usize;
        let mut f = vec![vec![0; k + 1]; n + 1];
        for (i, e) in events.iter().enumerate() {
            let p = events[..i].partition_point(|a| a[1] < e[0]);
            for j in 1..=k {
                // 为什么是 p 不是 p+1：上面算的是 >= startDay，-1 后得到 < startDay，但由于还要 +1，抵消了
                f[i + 1][j] = f[i][j].max(f[p][j - 1] + e[2]);
            }
        }
        f[n][k]
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(nk+n\log n)$，其中 $n$ 为 $\textit{events}$ 的长度。
空间复杂度：$\mathcal{O}(nk)$。

注：也可以交换 DP 的两个维度，外层循环枚举 $j$，内层循环枚举 $i$。预处理二分结果后，可以用滚动数组优化，做到 $\mathcal{O}(n)$ 的空间复杂度（时间复杂度不变）。留给感兴趣的读者实现。

专题训练

见下面动态规划题单的「§7.2 不相交区间」。

分类题单

欢迎关注 B站@灵茶山艾府

两种方法：最小堆 / 并查集（Python/Java/C++/Go/JS/Rust）

endlesscheng

2025年6月24日 11:13

方法一：按开始时间分组 + 最小堆

分析

观察一：第一天（即开始时间 $\textit{startDay}_i$ 的最小值）一定要参加会议，若不参加，岂不是白白浪费机会？比如有个会议是 $[1,1]$，不参加就错过了。

或者说，对于任意最优解，如果第一天什么也没做，我们总是可以把其中某个会议的参加时间改成第一天。

如果有多个会议的 $\textit{startDay}_i$ 都相同呢？比如有三个会议 $[1,1],[1,2],[1,3]$，参加哪个会议更好？

观察二：参加结束时间 $\textit{endDay}_i$ 最小的会议。如果第一天不参加会议 $[1,1]$，而是参加会议 $[1,2]$，那么第二天就没法参加会议 $[1,1]$ 了。

参加 $\textit{endDay}_i$ 最小的会议后，问题变成从第二天开始，解决剩余 $n-1$ 个会议的子问题。

需要知道哪些信息？

在第一天，可以参加哪些会议？

在第二天，可以参加哪些会议？

在第 $i$ 天，可以参加哪些会议？

若按照开始时间分组，那么在第 $i$ 天，开始时间为 $i$ 的会议就是新增的可以参加的会议。

此外，还需要知道在剩余可以参加的会议中，结束时间最小的会议。根据观察二，参加这个会议。

算法

把会议按照开始时间分组，用 $\textit{groups}[i]$ 表示所有开始时间为 $i$ 的会议的结束时间。

我们需要一个数据结构维护结束时间。这个数据结构需要支持如下操作：

添加结束时间。
查询结束时间的最小值。
删除最小的结束时间，表示我们参加这个会议，或者这个会议已过期（结束时间小于当前时间）。

最小堆完美符合要求。

在第 $i$ 天：

删除最小堆中结束时间小于 $i$ 的会议（已过期）。
把开始时间为 $i$ 的会议的结束时间，加到最小堆中。
如果最小堆不为空，那么弹出堆顶（参加会议），把答案加一。

###py

class Solution:
    def maxEvents(self, events: List[List[int]]) -> int:
        mx = max(e[1] for e in events) 

        # 按照开始时间分组
        groups = [[] for _ in range(mx + 1)]
        for e in events:
            groups[e[0]].append(e[1])

        ans = 0
        h = []
        for i, g in enumerate(groups):
            # 删除过期会议
            while h and h[0] < i:
                heappop(h)
            # 新增可以参加的会议
            for end_day in g:
                heappush(h, end_day)
            # 参加一个结束时间最早的会议
            if h:
                ans += 1
                heappop(h)
        return ans

###java

class Solution {
    public int maxEvents(int[][] events) {
        int mx = 0;
        for (int[] e : events) {
            mx = Math.max(mx, e[1]);
        }

        // 按照开始时间分组
        List<Integer>[] groups = new ArrayList[mx + 1];
        Arrays.setAll(groups, i -> new ArrayList<>());
        for (int[] e : events) {
            groups[e[0]].add(e[1]);
        }

        int ans = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = 0; i <= mx; i++) {
            // 删除过期会议
            while (!pq.isEmpty() && pq.peek() < i) {
                pq.poll();
            }
            // 新增可以参加的会议
            for (int endDay : groups[i]) {
                pq.offer(endDay);
            }
            // 参加一个结束时间最早的会议
            if (!pq.isEmpty()) {
                ans++;
                pq.poll();
            }
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    int maxEvents(vector<vector<int>>& events) {
        int mx = 0;
        for (auto& e : events) {
            mx = max(mx, e[1]);
        }

        // 按照开始时间分组
        vector<vector<int>> groups(mx + 1);
        for (auto& e : events) {
            groups[e[0]].push_back(e[1]);
        }

        int ans = 0;
        priority_queue<int, vector<int>, greater<>> pq;
        for (int i = 0; i <= mx; i++) {
            // 删除过期会议
            while (!pq.empty() && pq.top() < i) {
                pq.pop();
            }
            // 新增可以参加的会议
            for (int end_day : groups[i]) {
                pq.push(end_day);
            }
            // 参加一个结束时间最早的会议
            if (!pq.empty()) {
                ans++;
                pq.pop();
            }
        }
        return ans;
    }
};

###go

func maxEvents(events [][]int) (ans int) {
    mx := 0
    for _, e := range events {
        mx = max(mx, e[1])
    }

    // 按照开始时间分组
    groups := make([][]int, mx+1)
    for _, e := range events {
        groups[e[0]] = append(groups[e[0]], e[1])
    }

    h := &hp{}
    for i, g := range groups {
        // 删除过期会议
        for h.Len() > 0 && h.IntSlice[0] < i {
            heap.Pop(h)
        }
        // 新增可以参加的会议
        for _, endDay := range g {
            heap.Push(h, endDay)
        }
        // 参加一个结束时间最早的会议
        if h.Len() > 0 {
            ans++
            heap.Pop(h)
        }
    }
    return
}

type hp struct{ sort.IntSlice }
func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any   { a := h.IntSlice; v := a[len(a)-1]; h.IntSlice = a[:len(a)-1]; return v }

###js

var maxEvents = function(events) {
    let mx = 0;
    for (const e of events) {
        mx = Math.max(mx, e[1]);
    }

    // 按照开始时间分组
    const groups = Array.from({ length: mx + 1 }, () => []);
    for (const [startDay, endDay] of events) {
        groups[startDay].push(endDay);
    }

    let ans = 0;
    const pq = new MinPriorityQueue();
    for (let i = 0; i <= mx; i++) {
        // 删除过期会议
        while (!pq.isEmpty() && pq.front() < i) {
            pq.dequeue();
        }
        // 新增可以参加的会议
        for (const endDay of groups[i]) {
            pq.enqueue(endDay);
        }
        // 参加一个结束时间最早的会议
        if (!pq.isEmpty()) {
            pq.dequeue();
            ans++;
        }
    }
    return ans;
};

###rust

use std::collections::BinaryHeap;

impl Solution {
    pub fn max_events(events: Vec<Vec<i32>>) -> i32 {
        let mut mx = 0;
        for e in &events {
            mx = mx.max(e[1]);
        }

        // 按照开始时间分组
        let mut groups = vec![vec![]; (mx + 1) as usize];
        for e in events {
            groups[e[0] as usize].push(e[1]);
        }

        let mut ans = 0;
        let mut h = BinaryHeap::<i32>::new();
        for (i, g) in groups.into_iter().enumerate() {
            // 删除过期会议
            while let Some(end_day) = h.peek() {
                if -end_day >= i as i32 {
                    break;
                }
                h.pop();
            }
            // 新增可以参加的会议
            for end_day in g {
                h.push(-end_day); // 取相反数，变成最小堆
            }
            // 参加一个结束时间最早的会议
            if let Some(_) = h.pop() {
                ans += 1;
            }
        }
        ans
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(U+n\log n)$，其中 $n$ 是 $\textit{events}$ 的长度，$U=\max(\textit{endDay}_i)$。注意不是 $\mathcal{O}(U\log n)$，因为有 $n$ 个会议，所以在 $\mathcal{O}(U)$ 天中，只有 $\mathcal{O}(n)$ 天在做入堆出堆的操作。可以优化到 $\mathcal{O}(n\log n)$，留给读者思考。
空间复杂度：$\mathcal{O}(n+U)$。

方法二：按结束时间排序 + 并查集

把问题换个表述，大家就很熟悉了：

你有 $n$ 门课程要考试，第 $i$ 门课程可以复习的时间段为 $[\textit{startDay}_i, \textit{endDay}_i]$。对于每门课程，你可以选择时间段内的一天速通复习，一天最多复习一门课程。为了最大化可以复习的课程数，应该如何安排？

优先复习临考（$\textit{endDay}_i$ 小）的课程，即按照 $\textit{endDay}_i$ 从小到大排序。对于每门课，选择区间中最早的未被占用的那天复习。

这可以用并查集实现：

当 $i$ 被占用时，合并 $i$ 和 $i+1$，把 $i$ 指向 $i+1$。
如此一来，通过 $\text{find}(\textit{startDay}_i)$ 找到的值，就是 $\ge \textit{startDay}_i$ 的未被占用的最小值 $x$。如果 $x\le \textit{endDay}_i$，那么就可以在 $x$ 这一天复习。然后合并 $x$ 和 $x+1$，表示 $x$ 被占用。

###py

class Solution:
    def maxEvents(self, events: List[List[int]]) -> int:
        events.sort(key=lambda e: e[1])

        mx = events[-1][1]
        fa = list(range(mx + 2))

        def find(x: int) -> int:
            if fa[x] != x:
                fa[x] = find(fa[x])
            return fa[x]

        ans = 0
        for start_day, end_day in events:
            x = find(start_day)  # 查找从 start_day 开始的第一个可用天
            if x <= end_day:
                ans += 1
                fa[x] = x + 1  # 标记 x 已占用
        return ans

###java

class Solution {
    public int maxEvents(int[][] events) {
        Arrays.sort(events, (a, b) -> a[1] - b[1]);

        int mx = events[events.length - 1][1];
        int[] fa = new int[mx + 2];
        for (int i = 0; i < fa.length; i++) {
            fa[i] = i;
        }

        int ans = 0;
        for (int[] e : events) {
            int x = find(e[0], fa); // 查找从 startDay 开始的第一个可用天
            if (x <= e[1]) {
                ans++;
                fa[x] = x + 1; // 标记 x 已占用
            }
        }
        return ans;
    }

    private int find(int x, int[] fa) {
        if (fa[x] != x) {
            fa[x] = find(fa[x], fa);
        }
        return fa[x];
    }
}

###cpp

class Solution {
public:
    int maxEvents(vector<vector<int>>& events) {
        ranges::sort(events, {}, [](auto& e) { return e[1]; });

        int mx = events.back()[1];
        vector<int> fa(mx + 2);
        ranges::iota(fa, 0);

        auto find = [&](this auto&& find, int x) -> int {
            if (fa[x] != x) {
                fa[x] = find(fa[x]);
            }
            return fa[x];
        };

        int ans = 0;
        for (auto& e : events) {
            int x = find(e[0]); // 查找从 startDay 开始的第一个可用天
            if (x <= e[1]) {
                ans++;
                fa[x] = x + 1; // 标记 x 已占用
            }
        }
        return ans;
    }
};

###go

func maxEvents(events [][]int) (ans int) {
    slices.SortFunc(events, func(a, b []int) int { return a[1] - b[1] })

    mx := events[len(events)-1][1]
    fa := make([]int, mx+2)
    for i := range fa {
        fa[i] = i
    }

    var find func(int) int
    find = func(x int) int {
        if fa[x] != x {
            fa[x] = find(fa[x])
        }
        return fa[x]
    }

    for _, e := range events {
        x := find(e[0]) // 查找从 startDay 开始的第一个可用天
        if x <= e[1] {
            ans++
            fa[x] = x + 1 // 标记 x 已占用
        }
    }
    return
}

###js

var maxEvents = function(events) {
    events.sort((a, b) => a[1] - b[1]);

    const mx = events[events.length - 1][1];
    const fa = _.range(mx + 2);

    function find(x) {
        if (fa[x] !== x) {
            fa[x] = find(fa[x]);
        }
        return fa[x];
    }

    let ans = 0;
    for (const [startDay, endDay] of events) {
        const x = find(startDay); // 查找从 startDay 开始的第一个可用天
        if (x <= endDay) {
            ans++;
            fa[x] = x + 1; // 标记 x 已占用
        }
    }
    return ans;
};

###rust

impl Solution {
    pub fn max_events(mut events: Vec<Vec<i32>>) -> i32 {
        events.sort_unstable_by_key(|a| a[1]);

        let mx = events.last().unwrap()[1] as usize;
        let mut fa = (0..=mx+1).collect::<Vec<_>>();

        fn find(x: usize, fa: &mut [usize]) -> usize {
            if fa[x] != x {
                fa[x] = find(fa[x], fa);
            }
            fa[x]
        }

        let mut ans = 0;
        for e in events {
            let x = find(e[0] as usize, &mut fa); // 查找从 startDay 开始的第一个可用天
            if x <= e[1] as usize {
                ans += 1;
                fa[x] = x + 1; // 标记 x 已占用
            }
        }
        ans
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(U + n\log n)$，其中 $n$ 是 $\textit{events}$ 的长度，$U=\max(\textit{endDay}_i)$。
空间复杂度：$\mathcal{O}(U)$。

注：用哈希表实现并查集，可以做到 $\mathcal{O}(n\log n)$ 时间和 $\mathcal{O}(n)$ 空间。留给感兴趣的读者思考。

相似题目

贪心题单的「二、区间贪心」。
数据结构题单的「五、堆（优先队列）」。
数据结构题单的「§7.4 数组上的并查集」。

分类题单

欢迎关注 B站@灵茶山艾府

维护每个元素的出现次数（Python/Java/C++/Go）

endlesscheng

2021年5月16日 12:18

本质是 1. 两数之和。

遍历 $\textit{nums}_1$ 中的数，问题变成：

设 $x = \textit{nums}_1[i]$，计算 $\textit{nums}_2$ 中有多少个数等于 $\textit{tot} - x$。

用哈希表维护 $\textit{nums}_2$ 中每个元素的出现次数，即可 $\mathcal{O}(1)$ 获知。

注：遍历 $\textit{nums}_1$ 中的数，是因为数据范围显示 $\textit{nums}_1$ 的最大长度比 $\textit{nums}_2$ 的小，遍历 $\textit{nums}_1$ 相比遍历 $\textit{nums}_2$ 时间复杂度更低。

class FindSumPairs:
    def __init__(self, nums1: List[int], nums2: List[int]):
        self.nums1 = nums1
        self.nums2 = nums2
        self.cnt = Counter(nums2)

    def add(self, index: int, val: int) -> None:
        # 维护 nums2 每个元素的出现次数
        self.cnt[self.nums2[index]] -= 1
        self.nums2[index] += val
        self.cnt[self.nums2[index]] += 1

    def count(self, tot: int) -> int:
        ans = 0
        for x in self.nums1:
            ans += self.cnt[tot - x]
        return ans

class FindSumPairs:
    def __init__(self, nums1: List[int], nums2: List[int]):
        self.nums2 = nums2
        self.cnt1 = Counter(nums1)
        self.cnt2 = Counter(nums2)

    def add(self, index: int, val: int) -> None:
        # 维护 nums2 每个元素的出现次数
        self.cnt2[self.nums2[index]] -= 1
        self.nums2[index] += val
        self.cnt2[self.nums2[index]] += 1

    def count(self, tot: int) -> int:
        ans = 0
        for x, c1 in self.cnt1.items():
            ans += c1 * self.cnt2[tot - x]
        return ans

class FindSumPairs {
    private final int[] nums1;
    private final int[] nums2;
    private final Map<Integer, Integer> cnt = new HashMap<>();

    public FindSumPairs(int[] nums1, int[] nums2) {
        this.nums1 = nums1;
        this.nums2 = nums2;
        for (int x : nums2) {
            cnt.merge(x, 1, Integer::sum);
        }
    }

    public void add(int index, int val) {
        // 维护 nums2 每个元素的出现次数
        cnt.merge(nums2[index], -1, Integer::sum);
        nums2[index] += val;
        cnt.merge(nums2[index], 1, Integer::sum);
    }

    public int count(int tot) {
        int ans = 0;
        for (int x : nums1) {
            ans += cnt.getOrDefault(tot - x, 0);
        }
        return ans;
    }
}

class FindSumPairs {
    vector<int> nums1, nums2;
    unordered_map<int, int> cnt;

public:
    FindSumPairs(vector<int>& nums1, vector<int>& nums2) {
        this->nums1 = nums1;
        this->nums2 = nums2;
        for (int x : nums2) {
            cnt[x]++;
        }
    }

    void add(int index, int val) {
        // 维护 nums2 每个元素的出现次数
        cnt[nums2[index]]--;
        nums2[index] += val;
        cnt[nums2[index]]++;
    }

    int count(int tot) {
        int ans = 0;
        for (int x : nums1) {
            ans += cnt[tot - x];
        }
        return ans;
    }
};

type FindSumPairs struct {
nums1 []int
nums2 []int
cnt   map[int]int
}

func Constructor(nums1, nums2 []int) FindSumPairs {
cnt := map[int]int{}
for _, x := range nums2 {
cnt[x]++
}
return FindSumPairs{nums1, nums2, cnt}
}

func (p *FindSumPairs) Add(index, val int) {
// 维护 nums2 每个元素的出现次数
p.cnt[p.nums2[index]]--
p.nums2[index] += val
p.cnt[p.nums2[index]]++
}

func (p *FindSumPairs) Count(tot int) (ans int) {
for _, x := range p.nums1 {
ans += p.cnt[tot-x]
}
return
}

复杂度分析

时间复杂度：初始化是 $\mathcal{O}(m)$，$\texttt{add}$ 是 $\mathcal{O}(1)$，$\texttt{count}$ 是 $\mathcal{O}(n)$。其中 $n$ 是 $\textit{nums}_1$ 的长度，$m$ 是 $\textit{nums}_2$ 的长度。
空间复杂度：$\mathcal{O}(m+q)$。其中 $q$ 是 $\texttt{add}$ 的调用次数。代码没有删除哈希表中出现次数等于 $0$ 的元素。

相似题目

2671. 频率跟踪器

分类题单

欢迎关注 B站@灵茶山艾府

两种方法：哈希表 / 数组（Python/Java/C++/Go/JS/Rust）

endlesscheng

2025年7月3日 13:37

方法一：哈希表

用哈希表统计每个元素的出现次数。

然后遍历哈希表，其中 key 等于 value 的元素即为幸运数，取其最大值。如果不存在这样的元素，答案为 $-1$。

###py

class Solution:
    def findLucky(self, arr: List[int]) -> int:
        cnt = Counter(arr)
        ans = -1
        for x, c in cnt.items():
            if x == c:
                ans = max(ans, x)
        return ans

###py

class Solution:
    def findLucky(self, arr: List[int]) -> int:
        cnt = Counter(arr)
        return max((x for x, c in cnt.items() if x == c), default=-1)

###java

class Solution {
    public int findLucky(int[] arr) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int x : arr) {
            cnt.merge(x, 1, Integer::sum);
        }

        int ans = -1;
        for (Map.Entry<Integer, Integer> e : cnt.entrySet()) {
            int x = e.getKey();
            int c = e.getValue();
            if (x == c) {
                ans = Math.max(ans, x);
            }
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    int findLucky(vector<int>& arr) {
        unordered_map<int, int> cnt;
        for (int x : arr) {
            cnt[x]++;
        }

        int ans = -1;
        for (auto& [x, c] : cnt) {
            if (x == c) {
                ans = max(ans, x);
            }
        }
        return ans;
    }
};

###go

func findLucky(arr []int) int {
cnt := map[int]int{}
for _, x := range arr {
cnt[x]++
}

ans := -1
for x, c := range cnt {
if x == c {
ans = max(ans, x)
}
}
return ans
}

###js

var findLucky = function(arr) {
    const cnt = new Map();
    for (const x of arr) {
        cnt.set(x, (cnt.get(x) ?? 0) + 1);
    }

    let ans = -1;
    for (const [x, c] of cnt.entries()) {
        if (x === c) {
            ans = Math.max(ans, x);
        }
    }
    return ans;
};

###rust

use std::collections::HashMap;

impl Solution {
    pub fn find_lucky(arr: Vec<i32>) -> i32 {
        let mut cnt = HashMap::new();
        for x in arr {
            *cnt.entry(x).or_insert(0) += 1;
        }

        let mut ans = -1;
        for (x, c) in cnt {
            if x == c {
                ans = ans.max(x);
            }
        }
        ans
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\textit{nums}$ 的长度。
空间复杂度：$\mathcal{O}(n)$。

方法二：数组

由于一个数的出现次数不可能大于 $n$，所以大于 $n$ 的元素一定不是幸运数。我们只需统计 $\le n$ 的元素出现次数。

所以只需创建一个大小为 $n+1$ 的 $\textit{cnt}$ 数组统计。

###py

class Solution:
    def findLucky(self, arr: List[int]) -> int:
        n = len(arr)
        cnt = [0] * (n + 1)
        for x in arr:
            if x <= n:
                cnt[x] += 1

        for i in range(n, 0, -1):
            if cnt[i] == i:
                return i
        return -1

###java

class Solution {
    public int findLucky(int[] arr) {
        int n = arr.length;
        int[] cnt = new int[n + 1];
        for (int x : arr) {
            if (x <= n) {
                cnt[x]++;
            }
        }

        for (int i = n; i > 0; i--) {
            if (cnt[i] == i) {
                return i;
            }
        }
        return -1;
    }
}

###cpp

class Solution {
public:
    int findLucky(vector<int>& arr) {
        int n = arr.size();
        vector<int> cnt(n + 1);
        for (int x : arr) {
            if (x <= n) {
                cnt[x]++;
            }
        }

        for (int i = n; i > 0; i--) {
            if (cnt[i] == i) {
                return i;
            }
        }
        return -1;
    }
};

###c

int findLucky(int* arr, int arrSize) {
    int* cnt = calloc(arrSize + 1, sizeof(int));
    for (int i = 0; i < arrSize; i++) {
        if (arr[i] <= arrSize) {
            cnt[arr[i]]++;
        }
    }

    for (int i = arrSize; i > 0; i--) {
        if (cnt[i] == i) {
            free(cnt);
            return i;
        }
    }
    free(cnt);
    return -1;
}

###go

func findLucky(arr []int) int {
n := len(arr)
cnt := make([]int, n+1)
for _, x := range arr {
if x <= n {
cnt[x]++
}
}

for i := n; i >= 1; i-- {
if cnt[i] == i {
return i
}
}
return -1
}

###js

var findLucky = function(arr) {
    const n = arr.length;
    const cnt = Array(n + 1).fill(0);
    for (const x of arr) {
        if (x <= n) {
            cnt[x]++;
        }
    }

    for (let i = n; i > 0; i--) {
        if (cnt[i] === i) {
            return i;
        }
    }
    return -1;
};

###rust

impl Solution {
    pub fn find_lucky(arr: Vec<i32>) -> i32 {
        let n = arr.len();
        let mut cnt = vec![0; n + 1];
        for x in arr {
            if x as usize <= n {
                cnt[x as usize] += 1;
            }
        }

        for i in (1..=n).rev() {
            if cnt[i] as usize == i {
                return i as _;
            }
        }
        -1
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\textit{nums}$ 的长度。
空间复杂度：$\mathcal{O}(n)$。

思考题

动态地往 $\textit{arr}$ 中添加、删除元素，每次操作后，输出最大幸运数（不存在则为 $-1$）。

具体来说，额外输入一个 $\textit{queries}$ 数组，其中 $\textit{queries}[i] = [\textit{op}, x]$，如果 $\textit{op}=1$ 表示往 $\textit{arr}$ 中添加一个 $x$；如果 $\textit{op}=2$ 表示删除 $\textit{arr}$ 中的一个 $x$。你需要返回一个与 $\textit{queries}$ 等长的数组，表示每次操作后的答案。

欢迎在评论区分享你的思路/代码。

分类题单