2024-12-01：单面值组合的第 K 小金额。用go语言，给定一个整数数组 coins，表示不同面值的硬币，同时给出一个整数 k。你可以使用任意数量的这些硬币，但不能将不同面值的硬币组合在一起。请返回可以用这些硬币构成的第 k 个最小金额。

1 <= coins.length <= 15。

1 <= coins[i] <= 25。

$1 <= k <= 2 * 10^9$。

输入：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：

chatgpt

题目来自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));
}