class Solution {
public:
long long findKthSmallest(vector<int>& coins, int k) {
}
};
100267. 单面值组合的第 K 小金额
给你一个整数数组 coins 表示不同面额的硬币，另给你一个整数 k 。
你有无限量的每种面额的硬币。但是，你 不能 组合使用不同面额的硬币。
返回使用这些硬币能制造的 第 kth 小 金额。
示例 1：
输入： coins = [3,6,9], k = 3
输出： 9
解释：给定的硬币可以制造以下金额：
3元硬币产生3的倍数：3, 6, 9, 12, 15等。
6元硬币产生6的倍数：6, 12, 18, 24等。
9元硬币产生9的倍数：9, 18, 27, 36等。
所有硬币合起来可以产生：3, 6, 9, 12, 15等。
示例 2：
输入：coins = [5,2], k = 7
输出：12
解释：给定的硬币可以制造以下金额：
5元硬币产生5的倍数：5, 10, 15, 20等。
2元硬币产生2的倍数：2, 4, 6, 8, 10, 12等。
所有硬币合起来可以产生：2, 4, 5, 6, 8, 10, 12, 14, 15等。
提示：
1 <= coins.length <= 151 <= coins[i] <= 251 <= k <= 2 * 109coins 包含两两不同的整数。原站题解
golang 解法, 执行用时: 72 ms, 内存消耗: 2.2 MB, 提交时间: 2024-04-15 14:33:52
func findKthSmallest(coins []int, k int) int64 {
ans := sort.Search(slices.Min(coins)*k, func(m int) bool {
cnt := 0
next:
for i := uint(1); i < 1<<len(coins); i++ { // 枚举所有非空子集
lcmRes := 1 // 计算子集 LCM
for j := i; j > 0; j &= j - 1 {
lcmRes = lcm(lcmRes, coins[bits.TrailingZeros(j)])
if lcmRes > m { // 太大了
continue next
}
}
c := m / lcmRes
if bits.OnesCount(i)%2 == 0 {
c = -c
}
cnt += c
}
return cnt >= k
})
return int64(ans)
}
func gcd(a, b int) int {
for a != 0 {
a, b = b%a, a
}
return b
}
func lcm(a, b int) int {
return a / gcd(a, b) * b
}
python3 解法, 执行用时: 574 ms, 内存消耗: 16.6 MB, 提交时间: 2024-04-15 14:33:38
class Solution:
def findKthSmallest(self, coins: List[int], k: int) -> int:
def check(m: int) -> bool:
cnt = 0
for i in range(1, 1 << len(coins)): # 枚举所有非空子集
lcm_res = 1 # 计算子集 LCM
for j, x in enumerate(coins):
if i >> j & 1:
lcm_res = lcm(lcm_res, x)
if lcm_res > m: # 太大了
break
else: # 中途没有 break
cnt += m // lcm_res if i.bit_count() % 2 else -(m // lcm_res)
return cnt >= k
return bisect_left(range(min(coins) * k), True, k, key=check)
java 解法, 执行用时: 70 ms, 内存消耗: 40.7 MB, 提交时间: 2024-04-15 14:33:24
class Solution {
public long findKthSmallest(int[] coins, int k) {
int mx = Integer.MAX_VALUE;
for (int x : coins) {
mx = Math.min(mx, x);
}
long left = k - 1, right = (long) mx * k;
while (left + 1 < right) {
long mid = (left + right) / 2;
if (check(mid, coins, k)) {
right = mid;
} else {
left = mid;
}
}
return right;
}
private boolean check(long m, int[] coins, int k) {
long cnt = 0;
next:
for (int i = 1; i < (1 << coins.length); i++) { // 枚举所有非空子集
long lcmRes = 1; // 计算子集 LCM
for (int j = 0; j < coins.length; j++) {
if ((i >> j & 1) == 1) {
lcmRes = lcm(lcmRes, coins[j]);
if (lcmRes > m) { // 太大了
continue next;
}
}
}
cnt += Integer.bitCount(i) % 2 == 1 ? m / lcmRes : -m / lcmRes;
}
return cnt >= k;
}
private long lcm(long a, long b) {
return a * b / gcd(a, b);
}
private long gcd(long a, long b) {
return b == 0 ? a : gcd(b, a % b);
}
}
cpp 解法, 执行用时: 72 ms, 内存消耗: 19.2 MB, 提交时间: 2024-04-15 14:33:07
// 二分答案+容斥原理
class Solution {
public:
long long findKthSmallest(vector<int>& coins, int k) {
auto check = [&](long long m) -> bool {
long long cnt = 0;
for (int i = 1; i < (1 << coins.size()); i++) { // 枚举所有非空子集
long long lcm_res = 1; // 计算子集 LCM
for (int j = 0; j < coins.size(); j++) {
if (i >> j & 1) {
lcm_res = lcm(lcm_res, coins[j]);
if (lcm_res > m) { // 太大了
break;
}
}
}
cnt += __builtin_popcount(i) % 2 ? m / lcm_res : -m / lcm_res;
}
return cnt >= k;
};
long long left = k - 1, right = (long long) ranges::min(coins) * k;
while (left + 1 < right) {
long long mid = (left + right) / 2;
(check(mid) ? right : left) = mid;
}
return right;
}
};