每日算法刷题Day29 6.12:leetcode二分答案4道题，用时1h10min

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;} elseleft = 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小的数(困难,学习)

668. 乘法表中第k小的数 - 力扣（LeetCode）

思想

1.几乎每一个人都用 乘法表。但是你能在乘法表中快速找到第 k 小的数字吗？
乘法表是大小为 m x n 的一个整数矩阵，其中 mat[i][j] == i * j（下标从 1 开始）。
给你三个整数 m、n 和 k，请你在大小为 m x n 的乘法表中，找出并返回第 k 小的数字。
2.化简为二分答案x，满足<=x的数至少为k个，而对应第i行，个数就是$min(\lfloor \frac{x}{i}\rfloor ,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;} elseleft = 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;} elsecontinue;}}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;} elseleft = 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;} elsecontinue;}}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;} elseleft = 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; // 数对减1if (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;elsereturn 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;} elseleft = mid + 1;}return res % mod;}
};