随手连官方题解
2026-09-16 20:10:54
发布于：浙江
连线题这样连……不对，是随手练
1.解题思路
数据读取与利润计算
首先读取整数
n
n。
读取长度为
n
n 的收入数组
x
x 和支出数组
y
y。
遍历每一天
i
i（从
0
0 到
n
−
1
n−1），计算当天的利润：
p
r
o
f
i
t
i
x
i
−
y
i
profit
i
=x
i
−y
i
。
频次统计
由于需要统计每个利润值出现的次数，且利润值可能为负数，推荐使用 哈希表（Map/Dictionary） 或者 数组偏移法。
方法一：哈希表（推荐）
创建一个映射结构（如 C++ 的 stdmap 或 Python 的 dict / collections.Counter）。
Key 为利润值，Value 为该利润值出现的次数。
遍历计算出的所有利润值，在 map 中累加计数。
优势：stdmap 默认按键值（Key）升序排列，可以直接满足输出要求。
方法二：数组偏移（适合范围已知且较小）
题目中
0
≤
x
,
y
≤
100
0≤x,y≤100，所以利润范围在
[
−
100
,
100
]
[−100,100] 之间。
可以创建一个大小为 201 的数组 count[201]，初始化为 0。
将利润
p
p 映射到数组下标
p
+
100
p+100。
遍历利润，执行 count[p + 100]++。
结果输出
若使用哈希表（如 std::map）：
直接遍历 map，因为 Key 已经自动升序排列。
输出 Key（利润）和 Value（频次）。
若使用普通字典或数组：
需要收集所有出现过的利润值。
对这些利润值进行升序排序。
按排序后的顺序，依次输出利润及其对应的频次。
注意：只输出频次大于 0 的利润项。
2.这是一个经典的“从N个数中找出前M大的数并排序”的问题。考虑到数据范围
N
≤
1
0
6
N≤10
6
，我们需要选择时间复杂度较优的算法，避免
O
(
N
2
)
O(N
2
) 的暴力解法。
以下是几种可行的解题思路，按推荐程度排序：
思路一：全排序法（最简单、最稳妥）
虽然题目只要求前
M
M 个，但在
N
1
0
6
N=10
6
的规模下，现代计算机执行一次
O
(
N
log
N
)
O(NlogN) 的快速排序或归并排序通常只需几百毫秒，完全在 3000ms 的时间限制内。这是代码实现最简单且不易出错的方法。
读取数据：读取
n
,
m
n,m 和数组
a
a。
排序：将数组
a
a 进行降序排序（从大到小）。
如果使用 C++ std::sort，可以配合 greater<int>()。
如果使用 Python，可以使用 sorted(a, reverse=True)。
输出：取出排序后数组的前
m
m 个元素，用空格隔开输出。
时间复杂度：
O
(
N
log
N
)
O(NlogN)
空间复杂度：
O
(
1
)
O(1) 或
O
(
N
)
O(N)（取决于排序实现）
适用性：对于
1
0
6
10
6
的数据量，此方法完全可行且代码极简。
思路二：部分排序 / nth_element + 局部排序（效率更高）
如果追求更极致的效率，或者
M
M 远小于
N
N（例如
N
1
0
6
,
M
10
N=10
6
,M=10），可以使用基于快速选择（Quick Select）思想的算法。
寻找分界点：使用类似 stdnth_element 的算法，找到第
M
M 大的数，并将所有比它大的数移到数组的前部（或后部，取决于实现）。这一步平均时间复杂度为
O
(
N
)
O(N)。
局部排序：此时，前
M
M 个元素就是最大的
M
M 个数，但它们内部是无序的。对这
M
M 个元素进行排序，时间复杂度为
O
(
M
log
M
)
O(MlogM)。
输出：输出这
M
M 个已排序的元素。
总时间复杂度：
O
(
N
+
M
log
M
)
O(N+MlogM)
优势：当
M
≪
N
M≪N 时，比全排序快得多。
注意：C++ STL 中的 stdpartial_sort 可以直接完成这个任务。
思路三：最小堆（适合流式数据或内存受限）
维护一个大小为
M
M 的最小堆。
初始化：读取前
M
M 个数，建立最小堆。堆顶元素是当前
M
M 个数中最小的。
遍历剩余元素：对于后续的每个数
x
x：
如果
x
x> 堆顶元素，则弹出堆顶，将
x
x 入堆，并调整堆。
如果
x
≤
x≤ 堆顶元素，则忽略。
输出：遍历结束后，堆中剩下的
M
M 个数即为最大的
M
M 个数。由于堆是最小堆，输出时需要先将堆中元素取出并降序排序后再输出。
时间复杂度：
O
(
N
log
M
)
O(NlogM)
空间复杂度：
O
(
M
)
O(M)
适用性：适合
M
M 非常小的情况，或者数据无法一次性装入内存的场景。在本题中，由于
N
N 和
M
M 同阶可能较大，且需要最后排序，优势不如前两种明显，但也是标准解法之一。
3.这道题是经典的“去重+排序”问题。由于数据范围非常小（
N
≤
100
N≤100，数值范围
1
∼
1000
1∼1000），有多种解法均可轻松通过。以下提供三种主流思路，按推荐程度排序：
思路一：桶排序/标记数组法（最推荐，代码最简）
核心思想：利用题目中“数值在 1 到 1000 之间”这一关键条件。我们可以创建一个大小为 1001 的布尔数组（或整数数组）作为“桶”。数组的下标代表具体的数值，数组的值代表该数值是否出现过。
步骤：
初始化：创建一个长度为 1001 的数组 bucket，初始值全为 0（表示未出现）。
读取与标记：遍历输入的
N
N 个数。对于每个数
x
x，将 bucket[x] 设为 1。如果之前已经是 1，说明重复，无需额外操作，直接覆盖即可。同时可以统计有多少个不同的数被标记了（或者最后再统计）。
输出结果：
首先遍历 bucket 数组，统计值为 1 的个数，即为去重后的个数
M
M，输出
M
M。
再次从下标 1 到 1000 遍历 bucket 数组。如果 bucket[i] 为 1，则输出
i
i。因为下标本身就是从小到大排列的，所以输出的自然就是升序序列。
优点：
天然去重：同一个下标只能存一个状态，重复输入只会重复赋值，不会增加计数。
天然排序：遍历数组下标本身就是从小到大的顺序，无需调用排序算法。
时间复杂度：
O
(
N
+
K
)
O(N+K)，其中
K
1000
K=1000 是常数，效率极高。
4.这是一个经典的选择排序（Selection Sort）算法实现问题。虽然题目描述较为简略，但结合样例和标题，核心任务是读取一组整数，使用选择排序算法将其从小到大排序，并输出结果。
核心思路
选择排序的基本思想是：每一轮从未排序的部分中找到最小（或最大）的元素，将其放到已排序部分的末尾。
具体步骤如下：
外层循环：遍历数组的每一个位置
i
i（从
0
0 到
n
−
2
n−2），表示当前要确定第
i
i 个位置的最终元素。
内层查找：在未排序的子数组（从
i
+
1
i+1 到
n
−
1
n−1）中，寻找最小值的下标 min_index。
初始化 min_index = i。
遍历
j
j 从
i
+
1
i+1 到
n
−
1
n−1，如果 a[j] < a[min_index]，则更新 min_index = j。
交换：如果找到的最小值下标 min_index 不等于当前下标
i
i，则交换 a[i] 和 a[min_index]。
重复：直到所有位置都处理完毕。
算法演示
假设输入数组为 [3, 1, 2]：
第 1 轮 (
i
0
i=0)：
在 [3, 1, 2] 中找最小值。
比较发现 1 最小，下标为 1。
交换 a[0] 和 a[1]。
数组变为 [1, 3, 2]。此时 1 已就位。
第 2 轮 (
i
1
i=1)：
在剩余部分 [3, 2] 中找最小值。
比较发现 2 最小，下标为 2。
交换 a[1] 和 a[2]。
数组变为 [1, 2, 3]。此时 2 已就位。
结束：最后一个元素 3 自然就位。
输出：1 2 3
这里空空如也
有帮助，赞一个