【华为OD题库-093】购物-java

题目

商店里有N件唯一性商品，每件商品有一个价格，第i件商品的价格是ai。一个购买方案可以是从N件商品种选择任意件进行购买(至少—件)，花费即价格之和。
现在你需要求出所有购买方案中花费前K小的方案，输出这些方案的花费。当两个方案选择的商品集合至少有一件不同，视为不同方案，因此可能存在两个方案花费相同.
输入描述
输入数据含两行:
第一行包含两个整数N，K，整数之间通过空格隔开。分别表示商品的个数，以及需要求的花费个数。1<=N<=10000,1<=K<=min(2^N -1,100000)
第二行包含N个整数a1，a2，…an,整数之间通过空格隔开。表示N件商品的价格。1<=a1<= a2 …<= an <= 10000
输出描述
按花费从小到大的顺序依次输出K行，一行一个整数。表示花费前K小的购买方案的花费
示例1:
输入
5 6
1 1 2 3 3
输出
1
1
2
2
3
3
示例2:
输入
3 5
1 100 101
输出
1
100
101
101
102

思路

这道题比较有意思

求全组合的前K小，直观方法就是穷举所有组合，然后将结果排序，取前K，这样效率比较低，容易超时。可以考虑优先级队列实现。以：1 2 9 100 200为例：

1. 先将nums从小到大排序
2. 对于每一个数，只有取和不取两种状态，所以组合数为2^5种，同时需要排除都不取，所以一共有2^5-1中购买方案。题目也明确说明了K<=2^N-1。
3. 定义优先级队列queue<Integer []>，queue里面存两个数组成的数组，第一个数字表示当前累加和，第二个数字表示当前需要加的数在nums中的索引。
4. 初始状态：queue需要加入[0,0]的数据，代表累加和为0，结果加入nums[0]的数字，所以第一个组合为：1
5. 对于接下来的组合：可以考虑1选取和不选取两种情况，如果不选取，那么queue加下一个数：[0,1],如果选取，那么累加和需算上当前加入的值，即queue.add([1,1])
6. 依次类推，每次从queue中取最小的值（a[0]+nums[a[1]]）加入结果中，再考虑后续组合加上或者不加当前数字的两种情况即可。
7. 在向queue中加入数据时，注意a[1]不能超过nums的索引范围

题解

package hwod;

import leetcode.TreeNode;

import java.util.*;

public class Shoping {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        List<Integer> res = shoping(nums, k);
        for (int i = 0; i < k; i++) {
            System.out.println(res.get(i));
        }
    }

    private static List<Integer> shoping(int[] nums, int k) {
        List<Integer> res = new ArrayList<>();
        Arrays.sort(nums);
        PriorityQueue<Integer[]> queue = new PriorityQueue<>(Comparator.comparingInt(a -> a[0] + nums[a[1]]));
        //a[0]:之前的累加和；a[1]:当前准备增加数在nums中的索引
        queue.add(new Integer[]{0, 0});
        while (!queue.isEmpty() && res.size() < k) {
            Integer[] cur = queue.poll();
            int tmp = cur[0] + nums[cur[1]];
            res.add(tmp);
            if (cur[1] < nums.length - 1) {
                queue.offer(new Integer[]{tmp, ++cur[1]});
                queue.offer(cur);
            }
        }
        return res;
    }

}

推荐

如果你对本系列的其他题目感兴趣，可以参考华为OD机试真题及题解（JAVA），查看当前专栏更新的所有题目。