2024-12-01：单面值组合的第 K 小金额。用go语言，给定一个整数数组 coins，表示不同面值的硬币，同时给出一个整数 k。你可以使用任意数量的这些硬币，但不能将不同面值的硬币组合在一起。请返回可以用这些硬币构成的第 k 个最小金额。
1 <= coins.length <= 15。
1 <= coins[i] <= 25。
1 < = k < = 2 ∗ 1 0 9 1 <= k <= 2 * 10^9 1<=k<=2∗109。
输入：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等，12是第7个数。
答案2024-12-01：
题目来自leetcode3116。
大体步骤如下：
1.对给定的硬币面值数组 coins 进行排序，以便后续处理。
2.创建一个空数组 a 用于存放不同面值的硬币。
3.遍历排序后的硬币数组，对于每一个硬币 x：
-
遍历数组 a 中的每个元素 y，检查是否 x 能整除 y，如果可以，则跳过该硬币 x。
-
如果 x 不能整除任何已选中的硬币，则将 x 加入数组 a。
4.计算数组 a 的所有子集的最小公倍数，并根据每个子集包含硬币的数量对最小公倍数的正负号进行调整。
5.使用二进制位运算构建所有子集的最小公倍数。
6.使用二进制计数方法判断对应子集的硬币数量是否大于等于 k。
7.输出第 k 个最小金额。
总体而言，这个解决方案涉及对硬币面值进行排序、计算最小公倍数、二进制位运算等操作。时间复杂度取决于硬币面值数组的长度和 k，为 O(2^n * n + n^2 * log(n))，其中 n 为硬币数量。
额外空间复杂度为 O(2^n)。
Go完整代码如下：
package main
import (
"fmt"
"slices"
"sort"
"math/bits"
)
func findKthSmallest(coins []int, k int) int64 {
slices.Sort(coins)
a := coins[:0]
next:
for _, x := range coins {
for _, y := range a {
if x%y == 0 {
continue next
}
}
a = append(a, x)
}
subsetLcm := make([]int, 1<<len(a))
subsetLcm[0] = 1
for i, x := range a {
bit := 1 << i
for mask, l := range subsetLcm[:bit] {
subsetLcm[bit|mask] = lcm(l, x)
}
}
for i := range subsetLcm {
if bits.OnesCount(uint(i))%2 == 0 {
subsetLcm[i] *= -1
}
}
ans := sort.Search(a[0]*k, func(m int) bool {
cnt := 0
for _, l := range subsetLcm[1:] {
cnt += m / l
}
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
}
func main() {
coins := []int{5,2}
k := 7
fmt.Println(findKthSmallest(coins,k))
}
Rust完整代码如下：
use std::cmp::Ordering;
fn find_kth_smallest(coins: &[i32], k: i32) -> i64 {
let mut sorted_coins = coins.to_vec();
sorted_coins.sort_unstable();
let mut filtered_coins = Vec::new();
'next: for &x in &sorted_coins {
for &y in &filtered_coins {
if x % y == 0 {
continue 'next;
}
}
filtered_coins.push(x);
}
let n = filtered_coins.len();
let subset_lcm_size = 1 << n;
let mut subset_lcm = vec![1; subset_lcm_size];
for (i, &x) in filtered_coins.iter().enumerate() {
let bit = 1 << i;
for mask in 0..bit {
subset_lcm[bit | mask] = lcm(subset_lcm[mask], x);
}
}
for i in 0..subset_lcm_size {
if i.count_ones() % 2 == 0 {
subset_lcm[i] *= -1;
}
}
let max_search_value = filtered_coins[0] * k;
let mut low = 1;
let mut high = max_search_value;
while low < high {
let mid = (low + high) / 2;
let mut cnt = 0;
for &l in &subset_lcm[1..] {
cnt += mid / l;
}
if cnt >= k {
high = mid; // If we have enough counts, we try smaller value
} else {
low = mid + 1; // If not enough, we go higher
}
}
low as i64
}
fn gcd(a: i32, b: i32) -> i32 {
let mut a = a;
let mut b = b;
while a != 0 {
let temp = b;
b = a;
a = temp % a;
}
b
}
fn lcm(a: i32, b: i32) -> i32 {
a / gcd(a, b) * b
}
fn main() {
let coins = vec![5, 2];
let k = 7;
println!("{}", find_kth_smallest(&coins, k));
}
