LeetCode 小水题选做（更新中）
LeetCode 小水题选做
目录- LeetCode 小水题选做
- 4. 寻找两个正序数组的中位数
- 41. 缺失的第一个正数
- 328. 奇偶链表
- 6015. 统计可以被 K 整除的下标对数目
4. 寻找两个正序数组的中位数
题目链接
题目大意：
给定两个排好序的数组 \(a, b\)，长度分别为 \(n, m\)。设 \(c\) 为把 \(a\)、\(b\) 合并后再排好序的数组，求 \(c\) 的中位数。要求时间复杂度 \(\mathcal{O}(\log(n + m))\)（不计输入）。
一、初步转化：如何避免关于中位数的繁杂分类讨论
首先，根据 \(n + m\) 的奇偶性不同，中位数的定义略有不同。考虑将所有 \(n + m\) 个数放在一起，排好序，记为数列 \(c\)。则当 \(n + m\) 为奇数时，中位数是 \(c\) 里第 \(\lfloor\frac{n + m}{2}\rfloor + 1\) 个数；当 \(n + m\) 为偶数时，中位数是 \(c\) 里第 \(\frac{n + m}{2}\) 个数和第 \(\frac{n + m}{2} + 1\) 个数的平均数。如果我们能实现一个函数，传入 \(k\)，返回 \(c\) 中第 \(k\) 个数，那么原问题自然也就迎刃而解了。
至此，我们把原问题转化为：
给出数列 \(a, b\) 和数字 \(k\)，要求在 \(\mathcal{O}(\log(n + m))\) 时间里求出 \(c\) 中第 \(k\) 个数。
于是我们成功避免了关于中位数的繁杂分类讨论。接下来考虑转化后的问题。
二、一些不成熟的想法（想看正解可以跳过本节）
第一想法是先把两个数组归并排序，但是这样做时间复杂度至少为 \(\mathcal{O}(n + m)\)。
另一想法是二分：不妨假设答案在 \(a\) 中，那么我们在 \(a\) 里二分答案。在 \(\text{check}\) 时，我们要求出当前的 \(a_{\text{mid}}\) 在 \(c\) 里排第几，也就是说 \(a\) 和 \(b\) 中一共有多少个比 \(a_{\text{mid}}\) 小的数。\(a\) 里显然有 \(\text{mid} - 1\) 个，而求 \(b\) 里有多少个，则需要在 \(b\) 里再次二分（或者用 \(\texttt{C++}\) 自带的 lower_bound，时间复杂度是一样的）。于是，两次二分套起来，总时间复杂度是 \(\mathcal{O}(\log^2(n + m))\)，仍不能令人满意。
三、真正解法
\(c\) 里的数要么来自 \(a\)，要么来自 \(b\)。考虑 \(c\) 的前 \(k\) 个数中，有多少个数来自 \(a\)，记为 \(x\)。则有 \(k - x\) 个数来自 \(b\)。那么，必定有：\(\max(a_x, b_{k - x}) \leq \min(a_{x + 1}, b_{k - x + 1})\)，因为 \(c\) 前 \(k\) 个数中任意一个，一定小于等于后 \(n + m - k\) 中任意一个（注：此处默认在 \(a, b\) 的最前面、最后面分别塞一个 \(-\infty, +\infty\)，这样可以避免类似 \(x = 0\) 或 \(x = n\) 的这种尴尬的边界情况）。
另外，如果知道了 \(x\)，显然也就知道了我们要求的 \(c\) 中第 \(k\) 个数（它就是 \(\max(a_x, b_{k - x})\)）。
怎么求 \(x\) 呢？我们先随便猜一个值 \(x'\)。那么：
- 若 \(x' = x\)，根据刚才的讨论，有：\(\max(a_x, b_{k - x}) \leq \min(a_{x + 1}, b_{k - x + 1})\)。
- 若 \(x' < x\)，相当于前 \(k\) 个数里来自 \(a\) 的太少了，来自 \(b\) 的太多了，所以 \(a_{x'}\) 太小，而 \(b_{k - x'}\) 太大。应该从后 \(n + m - k\) 个数里把一些来自 \(a\) 的数拿到前面来，替换掉前 \(k\) 个数里来自 \(b\) 的数。因此，此时有：\(b_{k - x'} > a_{x' + 1}\)。
- 若 \(x' > x\)，与上一条同理：前 \(k\) 个数里来自 \(a\) 的太多了，来自 \(b\) 的太少了，所以 \(a_{x'}\) 太大，而 \(b_{k - x'}\) 太小。应该从后 \(n + m - k\) 个数里把一些来自 \(b\) 的数拿到前面来，替换掉前 \(k\) 个数里来自 \(a\) 的数。因此，此时有：\(a_{x'} > b_{k - x' + 1}\)。
想明白这些以后，我们发现，只要我们随便猜一个 \(x'\)，就能 \(\mathcal{O}(1)\) 判断出它是大了还是小了。于是可以二分 \(x'\)。至此，我们在 \(\mathcal{O}(\log(n + m))\) 的时间复杂度内解决了本题。
一个需要注意的细节是，可能的 \(x\) 的范围是 \([0, k] \cap [k - m, n] = [\max(0, k - m), \min(k, n)]\)。二分开始前这样设置好范围，就可以避免下标越界的问题。
参考代码：
class Solution {
public:
const int INF = 1e6 + 5;
int n, m;
double find(vector& a, vector& b, int K) {
int l = max(0, K - m), r = min(n, K);
// 前 K 个里有多少个来自 a
while (l <= r) {
int from_a = (l + r) >> 1; // mid
int from_b = K - from_a;
assert(from_b >= 0);
assert(from_b <= m);
int la, lb, ra, rb;
if (from_a == 0) la = -INF;
else la = a[from_a - 1];
if (from_b == 0) lb = -INF;
else lb = b[from_b - 1];
if (from_a == n) ra = INF;
else ra = a[from_a];
if (from_b == m) rb = INF;
else rb = b[from_b];
if (max(la, lb) <= min(ra, rb)) {
return max(la, lb);
} else {
if (la > rb) {
r = from_a - 1;
} else {
assert(lb > ra);
l = from_a + 1;
}
}
}
assert(0);
}
double findMedianSortedArrays(vector& nums1, vector& nums2) {
n = nums1.size();
m = nums2.size();
if ((n + m) & 1) {
return find(nums1, nums2, (n + m) / 2 + 1);
} else {
double x = find(nums1, nums2, (n + m) / 2);
double y = find(nums1, nums2, (n + m) / 2 + 1);
return (x + y) / 2.0;
}
}
};
41. 缺失的第一个正数
题目链接
题目大意：
给你一个长度为 \(n\) 的、未排序的整数数组 \(a\)，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 \(\mathcal{O}(n)\) 并且只使用常数级别额外空间的解决方案。
一个提示：
可以修改原数组。
方法一：
首先，一个观察是：答案只可能在 \([1, n + 1]\) 中。比方说，如果答案为 \(n + 2\)，那么需要 \(1,2,\dots n + 1\) 这 \(n + 1\) 个数全都出现过，而数组里只有 \(n\) 个数，故答案不可能为 \(n + 2\)。
于是可以有一个时间复杂度 \(\mathcal{O}(n)\)，但是需要 \(\mathcal{O}(n)\) 额外空间的做法：开一个大小为 \(n\) 的 \(\texttt{bool}\) 型数组 \(b_{1\dots n}\)。对于每个 \(a_i\)，若 \(a_i\in [1, n]\)，就令 \(b_{a_i} = 1\)。最后从 \(1\) 到 \(n\) 遍历 \(b\)，遇到的第一个 \(b_j = 0\) 的位置 \(j\) 就是答案（如果所有 \(b_j\) 都是 \(1\)，答案就是 \(n + 1\)）。
进一步优化，注意到在上述做法中，所有 \(a_i\notin [1, n]\) 的 \(a_i\)，它具体是几，其实不重要。不妨令这些 \(a_i\) 都为 \(0\)。那么 \(a\) 数组里的数值范围就只有 \([0, n]\)。但是，\(a\) 可是一个 \(\texttt{int}\) 类型的数组啊！这岂不是大大的浪费？于是想到，可以用 \(a_i\) 的前 \(19\) 个二进制位来存储原本要存的数（\(2^{19} - 1 = 524287 > n\)，足够存储）；第 \(20\) 个二进制位，把它当成 \(b_i\) 去使用。前 \(19\) 个二进制位和第 \(20\) 个二进制位互不影响，完全就和开两个数组效果一样。然后沿用之前的做法即可。时间复杂度 \(\mathcal{O}(n)\)，额外空间复杂度 \(\mathcal{O}(1)\)。
参考代码（方法一）：
class Solution {
public:
int n;
int firstMissingPositive(vector& nums) {
n = nums.size();
for (int i = 0; i < n; ++i) {
if (nums[i] <= 0 || nums[i] > n) {
nums[i] = 0;
}
}
for (int i = 0; i < n; ++i) {
int x = nums[i] & ((1 << 19) - 1);
if (x) {
assert(x <= n);
nums[x - 1] |= (1 << 19);
}
}
for (int i = 1; i <= n; ++i) {
if ((nums[i - 1] >> 19) == 0) {
return i;
}
}
return n + 1;
}
};
方法二：
我们考虑将 \(a\) 数组“恢复”成下面的形式：
如果数组中包含 \(x \in [1, n]\)，那么恢复后，数组的第 \(x\) 个元素为 \(x\)。（此处认为下标从 \(1\) 开始）
形式化地说，设恢复后的数组为 \(a'\)。那么 \(\{a'_i\} = \{a_i\}\)（这里是可重集），并且对于所有 \(x\in[1, n]\) 且 \(\exist i\) 使得 \(a_i = x\) 的 \(x\)，有 \(a'_x = x\)。
在恢复后，数组应当为 \(1, 2, \dots, n\) 的形式，但其中有若干个位置上的数是错误的，每一个错误的位置就代表了一个缺失的正数。
如何恢复？考虑依次遍历所有位置。假设当前遍历到 \(a_i\)。记 \(a_i = x\)。
- 若 \(x\notin[1, n]\)，直接跳过不管，继续遍历。
- 若 \(x\in [1, n]\)，我们需要把它放到 \(a_x\) 的位置上。考虑 \(a_x\) 位置上现在的数。
- 如果 \(a_x\) 已经等于 \(x\)，那么说明数组里原本就有多个 \(x\)，\(x\) 已经被恢复好了，而当前的 \(a_i\) 是多余的，我们跳过不管，继续遍历。
- 如果 \(a_x \neq x\)，我们 \(\text{swap}(a_i, a_x)\)。这样就把 \(x\) 放到 \(a_x\) 上了。不过现在 \(a_i\) 上又多了一个新的数。令 \(x\) 等于新的 \(a_i\)，我们重复上述操作，直到 \(x\notin[1,n]\) 或者 \(a_x = x\)。
因为每次交换都会使得一个数回到正确的位置，而已经回到正确位置上的数不会再移动，所以总交换次数最多为 \(\mathcal{O}(n)\)。
时间复杂度 \(\mathcal{O}(n)\)，额外空间复杂度 \(\mathcal{O}(1)\)。
参考代码（方法二）：
class Solution {
public:
int n;
int firstMissingPositive(vector& nums) {
n = nums.size();
for (int i = 0; i < n; ++i) {
while (nums[i] >= 1 && nums[i] <= n) {
int x = nums[i];
if (nums[x - 1] == x) {
break;
}
swap(nums[x - 1], nums[i]);
}
}
for (int i = 0; i < n; ++i) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return n + 1;
}
};
328. 奇偶链表
题目链接
这题本身很简单，我是想借这题讲一点链表操作中的小技巧。平时在 OI 中我很少使用这种用指针实现的“真正的链表”，所以对它不是很熟悉。
- 链表题往往让你返回链表的首元素地址。而你操作完之后手上拿着的往往是最后一个元素的地址。所以在一开始要把首元素地址备份一下。
- 要新建节点时，可以选择“把数值填写到当前节点上，再新建一个空白节点”，或者“先新建一个节点，把数值填写到新节点上”。这有点类似于 OI 里输出一个序列时，
cout << a[i] << " ";还是cout << " " << a[i];。在链表题中，我推荐使用后一种做法。因为无论哪种做法，最后都涉及到多出来一个节点，要删掉，前一种做法多出来的是尾节点，后一种做法多出来的是首节点。要删除首节点是很容易的，令首节点 = 首节点 -> next即可；而要删除尾节点就比较麻烦了，因为我们不知道倒数第二个节点是谁，需要用一个last记录。
参考代码：
class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
ListNode* a = new ListNode;
ListNode* b = new ListNode;
ListNode* heada = a;
ListNode* headb = b;
int x = 1;
while (head != NULL) {
if (x & 1) {
a -> next = new ListNode;
a = a -> next;
a -> val = head -> val;
} else {
b -> next = new ListNode;
b = b -> next;
b -> val = head -> val;
}
head = head -> next;
++x;
}
b -> next = NULL;
a -> next = headb -> next;
return heada -> next;
}
};
6015. 统计可以被 K 整除的下标对数目
题目链接
题目大意：
给定一个长度为 \(n\) 的正整数数组 \(a\) 和一个正整数 \(k\)。求有多少对下标 \((i, j)\) 满足 \(1\leq i < j\leq n\) 且 \((a_i\times a_j) \bmod k = 0\)。
数据范围：\(1\leq n, k, a_i\leq 10^5\)。（注：实测 \(\mathcal{O}(n\sqrt{n})\) 做法会超时）。
解法：
首先，可以令 \(a_i \leftarrow \gcd(a_i, k)\)，不会影响答案。
设 \(b_i = \frac{k}{a_i}\)。问题转化为，对每个 \(i\)，求有多少 \(j < i\) 满足 \(a_j\) 是 \(b_i\) 的倍数。
不妨先忽略 \(j < i\) 这个要求（即 \(j\) 可以是 \([1, n]\) 中任意数），设此时求出的答案为 \(\text{ans}'\)。此时，每对合法的下标会被算两次（也就是 \((i, j)\) 和 \((j, i)\)），此外 \((i, i)\) 的情况也会被算到。所以，设真正的答案为 \(\text{ans}\)，则 \(\text{ans'} = \text{ans}\cdot 2+\sum_{i = 1}^{n}[a_i^2\bmod k = 0]\)。我们求出 \(\text{ans}'\) 就能推出 \(\text{ans}\)。
考虑如何求 \(\text{ans}'\)。因为数值 \(k, a_i\) 的范围不大，我们可以预处理出一个数组 \(g\)，满足 \(g_x = \sum_{i = 1}^{n}[a_i\bmod x = 0]\)，也就是整个 \(a\) 中有多少数是 \(x\) 的倍数。再枚举 \(i\)，每次把 \(g_{b_i}\) 累加到 \(\text{ans}'\) 里即可。
如何预处理 \(g\)？先弄一个数组 \(f\)，满足 \(f_y = \sum_{i = 1}^{n}[a_i = y]\)，也就是数值 \(y\) 在 \(a\) 中出现了多少次。再对每个 \(x\)，暴力枚举 \(x\) 的所有倍数 \(y\)，把 \(f_y\) 累加到 \(g_x\) 里。这样做的时间复杂度是 \(\mathcal{O}(\sum_{i = 1}^{n} \frac{n}{i}) = \mathcal{O}(n\log n)\)。
其他部分都是线性的，所以整个算法的时间复杂度就是 \(\mathcal{O}(n\log n)\)。
参考代码：
class Solution {
public:
typedef long long ll;
static const int MAXN = 1e5;
int gcd(int a, int b) {
return (!b) ? a : gcd(b, a % b);
}
int n, f[MAXN + 5], g[MAXN + 5];
long long coutPairs(vector& a, int K) {
n = a.size();
for (int i = 0; i < n; ++i) {
a[i] = gcd(a[i], K);
f[a[i]]++;
}
for (int i = 1; i <= MAXN; ++i) {
for (int j = i; j <= MAXN; j += i) {
g[i] += f[j];
}
}
ll ans = 0;
for (int i = 0; i < n; ++i) {
ans += g[K / a[i]];
}
for (int i = 0; i < n; ++i) {
ans -= ((ll)a[i] * a[i] % K == 0);
}
assert(ans % 2 == 0);
ans /= 2;
return ans;
}
};