第 10 次实验

A. 小蓝鲸找数字

--> 题目描述

$n$ 个小蓝鲸们每个人选择一个自己最喜欢的整数，小蓝鲸们选中的整数无序的存放在一个长度为 $n$ 的数组 $nums$ 内。小蓝鲸们很好奇不被大家喜欢的最小正整数是多少？

请你找到给定数组 $nums$ 中未出现的最小正整数。

要求： 1. 时间复杂度为 $O(n)$；2. 只使用常数级别额外空间。

提示： 使用 scanf 进行输入。

--> 输入格式

第一行一个正整数 $n$ 表示 $nums$ 数组的长度

第二行 $n$ 个以空格分隔的整数

--> 输出格式

一个正整数，给定数组中未出现的最小正整数

--> 样例数据

--> 样例1

input

3
1 2 0

output

--> 样例2

input

4
3 4 -1 2

output

--> 样例3

input

13
5 1 8 14 2 12 2 3 7 -6 4 8 0

output

--> 数据规模与约定

$1 \leq nums.length \leq 4 \times 10^6$

$-2^{31} \leq nums[i] \leq 2^{31} - 1$

时间限制：1s

空间限制：32MB

Solution

技巧题，考虑原地哈希做法

如果不考虑空间复杂度，可以将给定的数组的每一个元素存放到哈希桶对应相等下标的位置（bucket[i] = i）

因为 $n$ 个数最多占据 $1\sim n$ 的下标，所以设置 $arr[n+1]$ 即可

不考虑空间复杂度的思路
int *arr = new int[n];
int *bucket = new int[n+1]; // 确保 arr[n] 存在

for(int i = 0; i < n; i++){
    if(arr[i] >= 1 && arr[i] <= n) bucket[i] = i;
}

for(int i = 1; i <= n; i++){
    if(bucket[i] != i){
        cout >> i; break;
    }
}

如果考虑空间复杂度限制，我们考虑原地交换而不是开额外数组：

if(arr[i] >= 1 && arr[i] <= n) swap(arr[i], arr[arr[i]]);

交换以后，arr[arr[i]] = arr[i] 相当于原来的 bucket[i] = i，并且原来处于 arr[arr[i]] 的值也没有被覆盖，而是交换到了 arr[i] 处，可以继续尝试交换：

考虑空间复杂度的核心思路
for (int i = 0; i <= n; i++) {
    // 注意这里是 while 而不是 if
    while (arr[i] >= 1 && arr[i] <= n && arr[i] != arr[arr[i]]) {
        swap(arr[arr[i]], arr[i]);
    }
}

最终得到完整程序，时间复杂度 $O(n)$，空间复杂度 $O(1)$（不考虑原数组开销）

Solution
#include <iostream>

using namespace std;
using ll = long long;

// 利用异或运算实现两个数的原地交换
void swap(int& a, int& b) {
    if (&a != &b) {
        a ^= b; b ^= a; a ^= b;
    }
}

void solve(){
    int n; cin >> n;
    int *arr = new int[n+1];

    for(int i = 0; i < n; i++) cin >> arr[i];
    for (int i = 0; i <= n; i++) {
        while (arr[i] >= 1 && arr[i] <= n && arr[i] != arr[arr[i]]) {
            swap(arr[arr[i]], arr[i]);
        }
    }
    for(int i = 1; i <= n; i++){
        if(arr[i] != i) {
            cout << i;
            return;
        }
    }
    cout << n+1;
}


signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t; 
    // cin >> t;            // multi testcases
    t = 1;              // single testcase

    while (t--){
        solve();
    }
    return 0;
}

这类题目一般被称为 mex 问题（Minimum Excluded value, mex）

B. 小蓝鲸舞会

--> 题目描述

为了庆祝即将到来的感恩节，小蓝鲸们举行了盛大的广场舞会。在挑选舞伴时，小蓝鲸们要求配对的两人之间身高差不能太大，但也不能太小。设数对 $(a,b)$ 由整数 $a$ 和 $b$ 组成，其数对距离定义为 $a$ 和 $b$ 的绝对差值。

给你一个从小到大排序好的小蓝鲸的身高数组 $nums$ 和一个整数 $k$ ，数对由 $nums[i]$ 和 $nums[j]$ 组成且满足 $0 \leq i < j < nums.length$。请返回所有数对距离中第 $k$ 小的数对距离。

--> 输入格式

第一行输入 $n$ 和 $k$，其中$n$表示数组长度。

第二行输入 $n$ 个数，代表从小到大排序好的小蓝鲸的身高数组。

--> 输出格式

输出所有数对距离中第 $k$ 小的数对距离。

--> 样例数据

--> 样例1

输入

3 3
1 2 3

输出

解释：数对和对应的距离如下：

(1,2)~1 -> (2,3)~1 -> (1,3)~2 距离第3小的数对是 (1,3)，距离为2。

--> 数据规模与约定

$ n = nums.length $

$ 2 \leq n \leq 10^4 $

$ 0 \leq nums[i] \leq 10^6 $

$ 1 \leq k \leq n \times (n - 1) / 2 $

时间限制：$1 \text{s}$

空间限制：$64 \text{MB}$

Solution

第一思路是使用大根堆存 $k$ 个小元素得到第 $k$ 小的元素，事实上枚举所有数对加上堆操作，时间复杂度可以达到 $O(n^2\log k)$，过不了这一题（而且 $k$ 很大时，大根堆的空间也超过了 $64 \text{MB}$ 限制）

现在我们换一个思路，考虑对“数对距离”进行二分答案。对于一个给定的“数对距离”，我们通过计算其为第几小的数对距离（具体来说，有多少个数对的距离不超过该数对的距离，记这个值为 res），从而根据 res 和 k 的大小关系调整二分区间，最终得到答案

核心是如何得到，对于数对距离 mid，数组中有多少个数对的距离不超过 mid：原数组有序，我们可以使用双指针法更加快速地获得结果，容易得到时间复杂度为 $O(n)$

int count(int mid, int n){
    int ans = 0, p = 0;
    // i 和 p 都只向右移动，因此时间复杂度不会是 O(n^2)
    for (int i = 0; i < n; ++i) {
        // 找到最小的 p，使得 arr[i] - arr[p] <= mid
        while (p < n && arr[i] - arr[p] > mid) ++p;
        // 对于当前的 arr[i]，从 arr[p] 到 arr[i-1] 的所有数与 arr[i] 的差值都不超过 mid
        ans += i - p;
    }
    return ans;
}

加上二分框架即可得到正解，时间复杂度 $O(n\log r)$，其中 $r$ 为二分查找起始右边界：

Solution
#include <iostream>

using namespace std;
using ll = long long;

int *arr;

int count(int mid, int n){
    int ans = 0, p = 0;
    for (int i = 0; i < n; ++i) {
        while (p < n && arr[i] - arr[p] > mid) ++p;
        ans += i - p;
    }
    return ans;
}

void solve(){
    int n, k; cin >> n >> k;
    arr = new int[n];
    for(int i = 0; i < n; i++){
        cin >> arr[i];
    }
    // 二分答案
    int l = 0, r = arr[n-1] - arr[0];
    while(l < r){
        int mid = l + (r - l) / 2;
        if(count(mid, n) < k){
            l = mid + 1;
        } else r = mid;
    }
    cout << l;
    delete[] arr;
}


signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t; 
    // cin >> t;            // multi testcases
    t = 1;              // single testcase

    while (t--){
        solve();
    }
    return 0;
}

C. 奇怪的二叉搜索树

--> 题目描述

小蓝鲸学习了二叉搜索树后，去 OJ 上找到了一个相关的题目练手。题目如下：

输入 $N$ 个数字，你需要把这 $N$ 个数字依次按照二叉搜索树的插入方法插入到一个初始为空树的二叉搜索树中。你需要依次输出输入中的后 $N-1$ 个数字在二叉搜索树中的父节点中保存的数字。

小蓝鲸觉得这个题目很简单，按照题意写了一发课上教的二叉搜索树，OJ 却提示 Time Limit Exceeded。机智的她马上想到：如果输入的数据是单调的，那么二叉搜索树就会退化成一条链，这样光插入所有输入数据就是 $O(N^2)$ 的复杂度了，肯定会超时呀。

这让她很奇怪。于是，她向乐于助人的你寻求帮助。

注意：本题可以使用 STL，例如：vector、queue、set和map等。

--> 输入格式

第一行为一个正整数 $N$，第二行为 $N$ 个以空格分隔的两两不同的正整数 $a_i$。

--> 输出格式

一行 $N-1$ 个以空格分隔的数字，代表输入中的后 $N-1$ 个数字在二叉搜索树中的父节点中保存的数字。

--> 示例

--> 输入

5
3 1 5 2 4

--> 输出

3 3 1 5

解释：生成的二叉搜索树为
1
2
3
4
5
     1(3)
   /      \
2(1)       3(5)
  \        /   
 4(2)    5(4)
节点表示为：输入编号（输入数据）

--> 数据规模与约定

$2 \leq N \leq 5 \times 10^4$

$1 \leq a_i \leq 2\times10^9$

时间限制： 1s

空间限制： 128MB

Solution

既然建树操作本身的最坏时间复杂度高，我们不妨跳过建树操作本身，通过二叉搜索树的建树逻辑判断找出每个节点的父节点（类比于求 WPL 的最小值并不需要真的建立哈夫曼树）

注意到：

(1) 二叉搜索树的中序遍历结果是单调递增的

(2) 给定一个中序遍历序列，指定一个节点，其前驱/后继节点都不一定是该节点的父节点，但是对于叶节点来说，其父节点一定是中序遍历结果下的前驱 or 后继节点

(3) 插入新的节点时，新节点一定是叶节点，所以满足 (2) 的后半句话，更具体地说：新节点要么是其插入位置前驱节点的右孩子，要么是后继节点的左孩子

--> 如何二选一判断呢？只要选择前驱/后继节点中更深的节点即可

(4) 具体到代码实现上，采用 set<int> 使插入操作自动有序（其本质是红黑树，一种二叉平衡搜索树），lower_bound 用于寻找插入位置（找到前驱）；unordered_map<int, int> 记录每个值对应节点的深度

概括一下

每次插入新的权值 val 时，它在二叉搜索树中的父节点一定是当前已插入数字中“比 val 小的最大值（前驱）”或“比 val 大的最小值（后继）”，并且这两者中更晚插入的是父节点

Solution
#include <iostream>
#include <set>
#include <unordered_map>

using namespace std;

void solve(){
    int n; 
    cin >> n;
    set<int> tree;                 // 维护中序遍历
    unordered_map<int, int> depth; // 记录深度

    for (int i = 0; i < n; i++) {
        int val; cin >> val;

        if (i == 0) {
            tree.insert(val);
            depth[val] = 0;     // 根节点深度为 0
            continue;
        }

        // >= val 的第一个元素
        auto it = tree.lower_bound(val);

        int parent;
        bool hasPred = false, hasSucc = false;
        int pred_val = 0, succ_val = 0;

        // 有后继？
        if (it != tree.end()) {
            hasSucc = true;
            succ_val = *it;
        }
        // 有前驱？
        if (it != tree.begin()) {
            hasPred = true;
            pred_val = *prev(it);
        }

        if (!hasPred) {
            // 没有前驱，只有后继
            parent = succ_val;
        } else if (!hasSucc) {
            // 没有后继，只有前驱
            parent = pred_val;
        } else {
            // 前驱和后继都存在，选深度更大的作为父节点
            if (depth[pred_val] > depth[succ_val]) parent = pred_val;
            else parent = succ_val;
        }

        cout << parent << " ";
        depth[val] = depth[parent] + 1;
        tree.insert(val);
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t; 
    // cin >> t;           // multi testcases
    t = 1;                // single testcase

    while (t--){
        solve();
    }
    return 0;
}

感觉上难度了，两个小时只写了第一题😰

2025-11-292025-11-30