2.6 第K小/大
例如数组 [1,1,1,2,2]，其中第 1 小、第 2 小和第 3 小的数都是 1，第 4 小和第 5 小的数都是 2。
第 k 小等价于：求最小的 x，满足 ≤x 的数至少(不是恰好) 有 k 个。
第 k 大等价于：求最大的 x，满足 ≥x 的数至少(不是恰好) 有 k 个。
注 1：一般规定 k 从 1 开始，而不是像数组下标那样从 0 开始。
注 2：部分题目也可以用堆解决。
1.套路
c++:
class Solution {
public:
bool check(int m, int n, int k, int mid) {
int cnt = 0;
for (int i = 1; i <= m; ++i) {
if (cnt >= k) // 满足条件
return true;
}
return false;
}
int findKthNumber(int m, int n, int k) {
int left = 1, right = m * n, res = 0;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (check(m, n, k, mid)) {
res = mid;
right = mid - 1;
} else
left = mid + 1;
}
return res;
}
};
2.题目描述
1(学习).几乎每一个人都用 乘法表。但是你能在乘法表中快速找到第 k 小的数字吗？
乘法表是大小为 m x n 的一个整数矩阵，其中 mat[i][j] == i * j（下标从 1 开始）。
给你三个整数 m、n 和 k，请你在大小为 m x n 的乘法表中，找出并返回第 k 小的数字(答案)。
2.给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。(答案）
请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。
3.数对 (a,b) 由整数 a 和 b 组成，其数对距离定义为 a 和 b 的绝对差值。
给你一个整数数组 nums 和一个整数 k ，数对由 nums[i] 和 nums[j] 组成且满足 0 <= i < j < nums.length 。返回 所有数对距离中第 k 小的数对距离(答案)。
4.一个正整数如果能被 a 或 b 整除，那么它是神奇的。
给定三个整数 n , a , b ，返回第 n 个神奇的数字(答案)。因为答案可能很大，所以返回答案 对 109 + 7 取模 后的值。
3.学习经验
(1)将寻找第K小/大元素转变为二分答案一个值x,让<=x/>=x的数至少有k个
1. 668.乘法表中第K小的数(困难,学习)
思想
1.几乎每一个人都用 乘法表。但是你能在乘法表中快速找到第 k 小的数字吗？
乘法表是大小为 m x n 的一个整数矩阵，其中 mat[i][j] == i * j（下标从 1 开始）。
给你三个整数 m、n 和 k，请你在大小为 m x n 的乘法表中，找出并返回第 k 小的数字。
2.化简为二分答案x，满足<=x的数至少为k个，而对应第i行，个数就是 m i n ( ⌊ x i ⌋ , n ) min(\lfloor \frac{x}{i} \rfloor,n) min(⌊ix⌋,n)(利用乘法表性质)
代码
c++:
class Solution {
public:
bool check(int m, int n, int k, int mid) {
int cnt = 0;
for (int i = 1; i <= m; ++i) {
cnt += min(mid / i, n);
if (cnt >= k)
return true;
}
return false;
}
int findKthNumber(int m, int n, int k) {
int left = 1, right = m * n, res = 0;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (check(m, n, k, mid)) {
res = mid;
right = mid - 1;
} else
left = mid + 1;
}
return res;
}
};
2. 378.有序矩阵中第K小的元素(中等)
378. 有序矩阵中第 K 小的元素 - 力扣（LeetCode）
思想
1.给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。
2.转化为二分查找x，使得矩阵中<=x的数至少有k个，因为矩阵每行升序，所以一旦有一个>x,则直接continue跳到下一行
代码
c++:
class Solution {
public:
bool check(vector<vector<int>>& matrix, int k, int mid) {
int cnt = 0, n = matrix.size();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] <= mid) {
++cnt;
if (cnt >= k)
return true;
} else
continue;
}
}
return false;
}
int kthSmallest(vector<vector<int>>& matrix, int k) {
int n = matrix.size();
int left = matrix[0][0], right = INT_MIN, res = 0;
for (int i = 0; i < n; ++i)
right = max(matrix[i][n - 1], right);
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (check(matrix, k, mid)) {
res = mid;
right = mid - 1;
} else
left = mid + 1;
}
return res;
}
};
3. 719.找出第K小的数对距离(中等,想到滑动窗口优化)
719. 找出第 K 小的数对距离 - 力扣（LeetCode）
思想
1.数对 (a,b) 由整数 a 和 b 组成，其数对距离定义为 a 和 b 的绝对差值。
给你一个整数数组 nums 和一个整数 k ，数对由 nums[i] 和 nums[j] 组成且满足 0 <= i < j < nums.length 。返回 所有数对距离中 第 k 小的数对距离。
2.二分答案x，转化为数对距离<=x的个数至少为k个，但目前只能想到两次遍历然后提前continue剪枝
3.这种两次遍历就要想到用滑动窗口(双指针)来优化，这是不定长滑动窗口求子数组个数类型，且是越短越合法，联系起上一章的内容了
代码
c++:
class Solution {
public:
bool check(vector<int>& nums, int k, int mid) {
int cnt = 0, n = nums.size();
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (nums[j] - nums[i] <= mid) {
++cnt;
if (cnt >= k)
return true;
} else
continue;
}
}
return false;
}
int smallestDistancePair(vector<int>& nums, int k) {
int n = nums.size();
sort(nums.begin(), nums.end());
int left = INT_MAX, right = nums[n - 1] - nums[0], res = 0;
for (int i = 0; i + 1 < n; ++i)
left = min(left, nums[i + 1] - nums[i]);
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (check(nums, k, mid)) {
res = mid;
right = mid - 1;
} else
left = mid + 1;
}
return res;
}
};
优化check:
bool check(vector<int>& nums, int k, int mid) {
int cnt = 0, n = nums.size();
for (int left = 0, right = 1; right < n; ++right) {
// right入窗口
// left不满足条件出窗口
while (left < right && nums[right] - nums[left] > mid)
++left;
// [i,right]满足条件
cnt += right - left + 1 - 1; // 数对减1
if (cnt >= k)
return true;
}
return false;
}
4. 878.第N个神奇数字(困难,二分右界优化和容斥原理)
思想
1.一个正整数如果能被 a 或 b 整除，那么它是神奇的。
给定三个整数 n , a , b ，返回第 n 个神奇的数字。因为答案可能很大，所以返回答案 对 109 + 7 取模 后的值。
2.二分答案为一个值x，让[1,x]满足条件的数的个数>=n,想到用容斥原理优化了，但是二分右边界写的INT_MAX,太大了，应该直接写min(a,b)*n就满足条件了，左边界也可以从1优化为min(a,b)
3.最大公约数和最小公倍数是基础知识
代码
c++:
class Solution {
public:
int mod = 1e9 + 7;
bool check(int n, int a, int b, long long mid, long long minbei) {
long long cnt = mid / a + mid / b - mid / minbei;
if (cnt >= n)
return true;
else
return false;
}
long long gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
int nthMagicalNumber(int n, int a, int b) {
long long maxyue = gcd(a, b);
long long minbei = 1LL * a / maxyue * b;
long long res = 0, left = min(a,b), right = 1LL * min(a, b) * n;
while (left <= right) {
long long mid = (left + ((right - left) >> 1));
if (check(n, a, b, mid, minbei)) {
res = mid;
right = mid - 1;
} else
left = mid + 1;
}
return res % mod;
}
};