Hard
题目描述
给你一个整数数组 coins 表示不同面额的硬币和一个整数 k。
你有无数个每种面额的硬币。但是，你不能将不同面额的硬币组合使用。
返回使用这些硬币能组成的第 k 小的金额。
示例 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 * 10^9coins包含不同的整数
提示：
- 二分搜索答案
x - 使用容斥原理计算能组成的不超过
x的不同金额数量
解题思路
这是一道经典的二分搜索 + 容斥原理问题。
核心思路：
二分搜索答案：在可能的金额范围内二分搜索第k小的金额。由于每种硬币都能产生无限个倍数，答案的上界可以设为
k * min(coins)。容斥原理计算方案数：对于给定的金额x，需要计算有多少个不大于x的正整数能被至少一种硬币整除。这正是容斥原理的经典应用场景。
容斥原理实现：
- 单个硬币c能整除的数有
x/c个 - 两个硬币c1,c2都能整除的数有
x/lcm(c1,c2)个 - 需要计算所有子集的贡献，奇数大小子集贡献为正，偶数大小子集贡献为负
- 单个硬币c能整除的数有
优化处理：首先去除冗余硬币（如果一个硬币是另一个硬币的倍数，则可以删除较大的），这样可以减少计算量。
算法流程：
- 预处理：去除冗余硬币
- 二分搜索：在[1, k*min(coins)]范围内搜索
- 对于每个mid值，用容斥原理计算不超过mid的可组成金额数量
- 如果数量≥k，说明答案在左半部分，否则在右半部分
代码实现
class Solution {
public:
long long findKthSmallest(vector<int>& coins, int k) {
// 去除冗余硬币
vector<int> filtered;
sort(coins.begin(), coins.end());
for (int coin : coins) {
bool redundant = false;
for (int prev : filtered) {
if (coin % prev == 0) {
redundant = true;
break;
}
}
if (!redundant) {
filtered.push_back(coin);
}
}
coins = filtered;
long long left = 1, right = (long long)k * coins[0];
while (left < right) {
long long mid = left + (right - left) / 2;
if (countAmounts(coins, mid) >= k) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
private:
long long gcd(long long a, long long b) {
return b == 0 ? a : gcd(b, a % b);
}
long long lcm(long long a, long long b) {
return a / gcd(a, b) * b;
}
long long countAmounts(vector<int>& coins, long long x) {
int n = coins.size();
long long count = 0;
// 容斥原理：枚举所有子集
for (int mask = 1; mask < (1 << n); mask++) {
long long currentLcm = 1;
int bits = 0;
for (int i = 0; i < n; i++) {
if (mask & (1 << i)) {
currentLcm = lcm(currentLcm, (long long)coins[i]);
bits++;
if (currentLcm > x) break; // 优化：如果LCM太大，跳出
}
}
if (currentLcm <= x) {
if (bits % 2 == 1) {
count += x / currentLcm;
} else {
count -= x / currentLcm;
}
}
}
return count;
}
};
class Solution:
def findKthSmallest(self, coins: List[int], k: int) -> int:
from math import gcd
from functools import reduce
def lcm(a, b):
return a * b // gcd(a, b)
def lcm_multiple(nums):
return reduce(lcm, nums)
# 去除冗余硬币
coins.sort()
filtered = []
for coin in coins:
redundant = False
for prev in filtered:
if coin % prev == 0:
redundant = True
break
if not redundant:
filtered.append(coin)
coins = filtered
def countAmounts(x):
n = len(coins)
count = 0
# 容斥原理：枚举所有非空子集
for mask in range(1, 1 << n):
subset = []
for i in range(n):
if mask & (1 << i):
subset.append(coins[i])
current_lcm = lcm_multiple(subset)
if current_lcm <= x:
if len(subset) % 2 == 1:
count += x // current_lcm
else:
count -= x // current_lcm
return count
left, right = 1, k * min(coins)
while left < right:
mid = (left + right) // 2
if countAmounts(mid) >= k:
right = mid
else:
left = mid + 1
return left
public class Solution {
public long FindKthSmallest(int[] coins, int k) {
// 去除冗余硬币
Array.Sort(coins);
var filtered = new List<int>();
foreach (int coin in coins) {
bool redundant = false;
foreach (int prev in filtered) {
if (coin % prev == 0) {
redundant = true;
break;
}
}
if (!redundant) {
filtered.Add(coin);
}
}
coins = filtered.ToArray();
long left = 1, right = (long)k * coins[0];
while (left < right) {
long mid = left + (right - left) / 2;
if (CountAmounts(coins, mid) >= k) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
private long Gcd(long a, long b) {
return b == 0 ? a : Gcd(b, a % b);
}
private long Lcm(long a, long b) {
return a / Gcd(a, b) * b;
}
private long CountAmounts(int[] coins, long x) {
int n = coins.Length;
long count = 0;
// 容斥原理：枚举所有子集
for (int mask = 1; mask < (1 << n); mask++) {
long currentLcm = 1;
int bits = 0;
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) {
currentLcm = Lcm(currentLcm, (long)coins[i]);
bits++;
if (currentLcm > x) break;
}
}
if (currentLcm <= x) {
if (bits % 2 == 1) {
count += x / currentLcm;
} else {
count -= x / currentLcm;
}
}
}
return count;
}
}
var findKthSmallest = function(coins, k) {
function gcd(a, b) {
return b === 0 ? a : gcd(b, a % b);
}
function lcm(a, b) {
return (a * b) / gcd(a, b);
}
// Remove redundant coins (coins that are multiples of other coins)
coins.sort((a, b) => a - b);
let filtered = [];
for (let i = 0; i < coins.length; i++) {
let isMultiple = false;
for (let j = 0; j < filtered.length; j++) {
if (coins[i] % filtered[j] === 0) {
isMultiple = true;
break;
}
}
if (!isMultiple) {
filtered.push(coins[i]);
}
}
coins = filtered;
function countAmounts(limit) {
let count = 0;
let n = coins.length;
// Use inclusion-exclusion principle
for (let mask = 1; mask < (1 << n); mask++) {
let currentLcm = 1;
let bits = 0;
for (let i = 0; i < n; i++) {
if (mask & (1 << i)) {
currentLcm = lcm(currentLcm, coins[i]);
bits++;
if (currentLcm > limit) break;
}
}
if (currentLcm <= limit) {
if (bits % 2 === 1) {
count += Math.floor(limit / currentLcm);
} else {
count -= Math.floor(limit / currentLcm);
}
}
}
return count;
}
let left = 1, right = k * coins[0];
while (left < right) {
let mid = Math.floor((left + right) / 2);
if (countAmounts(mid) < k) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
};
复杂度分析
| 复杂度 | 分析 |
|---|---|
| 时间复杂度 | O(log(k·min(coins)) · 2^n · n²) |
| 空间复杂度 | O(n) |
其中 n 是去重后的硬币数量（最多15个），每次二分需要 O(2^n · n²) 时间计算容斥原理。