请各位大佬帮我看看这道题，谢谢！
0 悬赏园豆： 200 [待解决问题] 题目描述
YJC最近在steam.上氪了不少金，但他还想氪更多。steam保证了不同的两款游戏的价格一定不同，并且游戏的价格- - 定是正整数。现在YJC已经买下了n款不同的游戏，价格分别为a1、a2、 .... an。 YJC手头还有m元，他想知道他最多还能入手多少款他没有的游戏?
输入
第一行包含两个整数n和m,表示YJC已经买下的游戏数和YJC的钱数。
第二行包含n个整数a,表示YJC已经入手的每一款游戏。
输出
第一行包含-一个整数k，表示YJC最多还能买下多少款游戏。
第二行包含k个整数b,表示YJC接下来要买下的每一款游戏。 如果有多组解，输出
字典序最小的。
样例输入
4 14
4 6 8 12
样例输出
4
1 2 3 5
提示
对于100%的数据，满足1<=n<=10的5次，1<=m,ai<,10的9次。 北城柳絮飘 | 初学一级 | 园豆： 2
提问于：2020-08-20 08:37 显示帮助
使用"Ctrl+Enter"可进行快捷提交，评论支持部分 Markdown 语法：[link](http://example.com) _italic_ **bold** `code`。
< > 分享
分享您的问题
所有回答(3) 0 题目的出处是啥？ Conan-jine | 园豆：927 (小虾三级) | 2020-08-20 12:31 正睿oi 支持( 0 ) 反对( 0 ) 北城柳絮飘 | 园豆：2 (初学一级) | 2020-08-20 12:32 编辑文本 预览 上传图片
Ctrl+Enter键快速提交 0 类似这样？
private static void gameCnt(int n, int m, Integer[] mArr) {
System.out.println("n:" + n + ", m:" + m + "mArr:" + Arrays.toString(mArr));
if(null == mArr || n < 0 || n != mArr.length){
System.out.println("fail");
return;
}
List<Integer> ml = Arrays.asList(mArr);
int i = 1;
List<Integer> wm = new ArrayList<>();
while(m > 0 && m >= i){
if(!ml.contains(i)){
wm.add(i);
m = m - i;
}
i++;
}
System.out.println(wm);
} WMG-Eight | 园豆：204 (菜鸟二级) | 2020-08-20 12:31 谢谢 支持( 0 ) 反对( 0 ) 北城柳絮飘 | 园豆：2 (初学一级) | 2020-08-20 12:32 编辑文本 预览 上传图片
Ctrl+Enter键快速提交 0 文字很长，核心重点：两款游戏的价格一定不同且价格一定是正整数。
所以整个题目可以简单化为：YJC 有一个整数列表x和一个整数m。从正整数a=1开始逐渐+1遍历，如果不在列表x中，则加入返回列表y中，且m-a。
实现如下： [Theory] [InlineData(new int[] { 4, 6, 8, 12 }, 14, 4)] public void SampleTest(int[] owned, int money, int expectBuyCount) { int price = 1; //游戏价格 int count = 0; //可买数量 List<int> buy = new List<int>(); //可买游戏价格表 while (money > 0) { //钱不够了 if (money < price) { break; } //已经买过了 if (owned.Contains(price)) { price++; continue; } //买下游戏 money = money - price; buy.Add(price); price++; count++; } Assert.True(expectBuyCount == count); }
优化点：
每次都要去owned列表中去判断存不存在，考虑优化
1.把owned列表转为hash表，这样每次判断o(1)的时间复杂度
2.如果owned列表是有序的，可以遍历owned列表，然后每次遍历owned列表i和i+1之间的整数，即为可买的数 xiaogui340 | 园豆：547 (小虾三级) | 2020-08-20 16:25 编辑文本 预览 上传图片
Ctrl+Enter键快速提交
清除回答草稿
您需要 登录 以后才能回答，未注册用户请先 注册 。