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

本文主要是介绍【华为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为例：

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