5. 1201.丑数III(中等)

1201. 丑数 III - 力扣（LeetCode）

思想

1.丑数是可以被 a 或 b 或 c 整除的 正整数 。
给你四个整数：n 、a 、b 、c ，请你设计一个算法来找出第 n 个丑数。
2.此题是4. 878.第N个神奇数字的进阶版，从两个数的容斥原理变成三个数的容斥原理，同理即可

代码

c++:

class Solution {
public:bool check(int n, int a, int b, int c, long long bei_ab, long long bei_ac,long long bei_bc, long long bei_abc, long long mid) {long long cnt = 0;cnt = mid / a + mid / b + mid / c - mid / bei_ab - mid / bei_ac -mid / bei_bc + mid / bei_abc;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 nthUglyNumber(int n, int a, int b, int c) {long long bei_ab = 1LL * a / gcd(a, b) * b;long long bei_ac = 1LL * a / gcd(a, c) * c;long long bei_bc = 1LL * b / gcd(b, c) * c;long long bei_abc = 1LL * bei_ab / gcd(bei_ab, c) * c;long long left = min({a, b, c}), right = min({a, b, c}) * n, res = 0;while (left <= right) {long long mid = left + ((right - left) >> 1);if (check(n, a, b, c, bei_ab, bei_ac, bei_bc, bei_abc, mid)) {res = mid;right = mid - 1;} elseleft = mid + 1;}return res;}
};

6. 373.查找和最小的K对数字(中等,学习优先队列小顶堆)

373. 查找和最小的 K 对数字 - 力扣（LeetCode）

思想

1.给定两个以 非递减顺序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。
定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。
请找到和最小的 k 个数对 (u1,v1), (u2,v2) … (uk,vk) 。
2.一开始想的是二分答案和最小的第k个和，但是check函数里面双指针不好写判断，所以学习优先队列最小堆写法
3.因为是按照和最小排序，所以最小堆比较的元素一定是和，即priority_queue的第一个元素是和，但是也要记录下标(i,j)从而能访问下一个元素，所以优先队列里面元素是三元组turple<int,int,int>,而优先队列默认是升序最大堆，且没有三元组的降序最小堆写法，需自己写，为了简单存入和的负值即可
接下来考虑入堆,目前元素为(i,j),下一个入堆元素为(i+1,j)或者(i,j+1),但是会出现一个问题,(i+1,j)入堆，然后(i+1,j+1)入堆，而如果(i,j+1)入堆，然后(i+1,j+1)又会入堆一次，导致(i+1,j+1)入堆两次，解决办法是先让所有(i,0)入堆(数量小于k),然后接下来入堆的只有(i,j+1)了(即固定i更新j)

代码

c++:

class Solution {
public:vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2,int k) {int n1 = nums1.size(), n2 = nums2.size();priority_queue<tuple<int, int, int>> pq;vector<vector<int>> res;for (int i = 0; i < min(n1, k); ++i) {pq.emplace(-nums1[i] - nums2[0], i, 0); // 先让所有(i,0)入堆,因为是小根堆，所以放负值}while (res.size() < k && !pq.empty()) {auto t = pq.top();pq.pop();int i = get<1>(t), j = get<2>(t);res.push_back({nums1[i], nums2[j]});if (j + 1 < n2)pq.emplace(-nums1[i] - nums2[j + 1], i, j + 1); //优先队列不是顺序访问，所以不用加back}return res;}
};

学习:
1.三元组tuple<int,int,int> t,访问三个元素get<0/1/2>(t)
2.vector,deque,list这些顺序访问才是push_back和emplace_back,且vector<vector<int>>插入一整行要用push_back({i,j}),不能用emplace_back(i,j)
而prioriyt_queue这些非顺序访问是emplace