- 2022/05/18
- 2022/05/19
- 2022/05/20
- Date
2022/05/18
链接： 668. 乘法表中第k小的数
解题思路：
由于
m
m
m 和
n
n
n 很大，直接求出所有数字然后找到第
k
k
k 小会超出时间限制。不妨考虑一个反向问题：对于乘法表中的数字
x
x
x ，它是乘法表中第几小的数字？
求第几小等价于求有多少数字不超过
x
x
x 。我们可以遍历乘法表的每一行，对于乘法表的第
i
i
i 行，其数字均为
i
i
i 的倍数，因此不超过
x
x
x 的数字有
min
(
⌊
x
i
⌋
,
n
)
min(Biglfloordfrac{x}{i}Bigrfloor,n)
min(⌊ix⌋,n) 个，所以整个乘法表不超过
x
x
x 的数字个数为
∑
i
=
1
m
min
(
⌊
x
i
⌋
,
n
)
sum_{i=1}^{m} min(Biglfloordfrac{x}{i}Bigrfloor,n)
i=1∑mmin(⌊ix⌋,n)
由于
i
≤
⌊
x
n
⌋
ile Biglfloordfrac{x}{n}Bigrfloor
i≤⌊nx⌋ 时
⌊
x
i
⌋
≥
n
Biglfloordfrac{x}{i}Bigrfloor ge n
⌊ix⌋≥n ，上式可化简为
⌊
x
n
⌋
⋅
n
+
∑
i
=
⌊
x
n
⌋
+
1
m
⌊
x
i
⌋
Biglfloordfrac{x}{n}Bigrfloorcdot n + sum_{i=Biglfloordfrac{x}{n}Bigrfloor+1}^{m} Biglfloordfrac{x}{i}Bigrfloor
⌊nx⌋⋅n+i=⌊nx⌋+1∑m⌊ix⌋
由于
x
x
x 越大上式越大，
x
x
x 越小上式越小，因此我们可以二分
x
x
x 找到答案，二分的初始边界为乘法表的元素范围，即
[
1
,
m
n
]
[1,mn]
[1,mn]。
作者：LeetCode-Solution
链接：https://leetcode.cn/problems/kth-smallest-number-in-multiplication-table/solution/cheng-fa-biao-zhong-di-kxiao-de-shu-by-l-521a/
来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
代码：
class Solution {
public:
int findKthNumber(int m, int n, int k) {
int left = 1, right = m * n; //左边界与右边界
while (left < right) {
int x = left + (right - left) / 2; // 二分查找中间值
int count = x / n * n;
for (int i = x / n + 1; i <= m; ++i) {
count += x / i;
} // x前面有多少个数
if (count >= k) { // 往前查找
right = x;
} else { // 往后查找
left = x + 1;
}
}
return left;
}
};
2022/05/19
链接：462. 最少移动次数使数组元素相等 II
解题思路：
直观的思路是全都改成中位数。
证明：【负雪明烛】图解算法：为什么选择中位数
我的代码：
class Solution {
public:
int minMoves2(vector& nums) {
int n = nums.size();
if(n == 1) return 0;
sort(nums.begin(), nums.end());
int mid = nums[n/2];
int cnt = 0;
for(int i = 0; i < n; i ++) {
cnt += abs(nums[i]-mid);
}
return cnt;
}
};
2022/05/20
链接：436. 寻找右区间
解题思路：
首先我们可以对区间
intervals
textit{intervals}
intervals 的左端点进行排序，并将每个左端点
intervals
[
i
]
[
0
]
textit{intervals}[i][0]
intervals[i][0] 与对应的索引
i
i
i 存储在数组
startIntervals
textit{startIntervals}
startIntervals 中，然后枚举每个区间
i
i
i 的右端点
intervals
[
i
]
[
1
]
textit{intervals}[i][1]
intervals[i][1]，利用二分查找在
startIntervals
textit{startIntervals}
startIntervals 中 找到大于等于
intervals
[
i
]
[
1
]
textit{intervals}[i][1]
intervals[i][1] 的最小值
val
textit{val}
val 即可，此时区间
i
i
i 对应的右侧区间即为右端点
val
textit{val}
val 对应的索引。
代码：
class Solution {
public:
vector findRightInterval(vector>& intervals) {
vector> startIntervals;
int n = intervals.size();
for (int i = 0; i < n; i++) {
startIntervals.emplace_back(intervals[i][0], i); //存储intervals的左端点及其对应的索引
}
sort(startIntervals.begin(), startIntervals.end()); //对intervals的左端点进行升序排序
vector ans(n, -1); //初始化返回区间索引
for (int i = 0; i < n; i++) {// 枚举右端点
auto it = lower_bound(startIntervals.begin(), startIntervals.end(), make_pair(intervals[i][1], 0));//二分查找不大于(intervals[i][1], 0)的第一个元素
if (it != startIntervals.end()) { // 存在右区间
ans[i] = it->second;
}
}
return ans;
}
};
Note：
-
emplace_back()函数是 C++ 11 新增加的，其功能和 push_back() 相同，都是在vector 容器的尾部添加一个元素。
emplace_back() 和 push_back() 的区别，就在于底层实现的机制不同。push_back() 向容器尾部添加元素时，首先会创建这个元素，然后再将这个元素拷贝或者移动到容器中（如果是拷贝的话，事后会自行销毁先前创建的这个元素）；而 emplace_back() 在实现时，则是直接在容器尾部创建这个元素，省去了拷贝或移动元素的过程。
mplace_back() 的执行效率比 push_back() 高。因此，在实际使用时，建议大家优先选用 emplace_back()。
参考链接：C++ STL vector添加元素（push_back()和emplace_back()）详解 -
lower_bound() 函数用于在指定区域内查找不小于目标值的第一个元素。
C++ 中 find()、find_if()、search() 等的底层实现都采用的是顺序查找（逐个遍历）的方式，在某些场景中的执行效率并不高。例如，当指定区域内的数据处于有序状态时，如果想查找某个目标元素，更推荐使用二分查找的方法 （相比顺序查找，二分查找的执行效率更高）。
C++ STL标准库中提供有 lower_bound()、upper_bound()、equal_range() 以及 binary_search() 这 4 个查找函数，它们的底层实现采用的都是二分查找的方式。
参考链接：C++ lower_bound()函数用法详解
【模板】
Date链接：
解题思路：
我的代码：
