笔试挂在这道题上面了，求高效解题思路

[techme]

如题，前两题比较简单，第三题还没有头绪就一不留神超时了 *换算几天后星期几 *x 轴上点之间最大距离 *在数组里面找出 K 个数加起来得到最大的偶数和 答题是在个类似 LeetCode 的网站上，会有跑分，优化会影响得分 这次是因为刷题少吃了亏，凌晨时候一点思路都没得

[guyeu]

第三个题可以转化为数组内最小的正奇数是几。。。

[techme]

@guyeu
是不是这样，如果 K 是 3，那么结果就可能是 （奇+奇+偶）（偶+偶+偶）
在我排序数组后
找到最大的两个奇数和最大的一个偶数
找到最大的三个偶数
然后比较它们和的大小

[Biggoldfish]

排个序，把前 K 个加起来得到一个和，和是偶数直接返回；和是奇数的话，把前 K 个中最小的奇数换成后面 N - K 个中最大的偶数 或者 把前 K 个中最小的偶数换成后面 N - K 个中最大的奇数，答案一定是两者中较大的一个，如果两者均为奇数，return -1 。

[guyeu]

@techme #2 去掉所有的负数，求和，如果和是奇数，就减去最小的奇数返回，如果和是偶数，就直接返回。

[rabbbit]

function isEven(num) {
...return num % 2 === 0;
}

function solution(A, K) {
...if (K === 0) {
......return -1;
...}
...let maxNum = -1;
...function dp(i, sum, remain) {
......if (remain === 0) {
.........if (isEven(sum) && sum > maxNum) {
............maxNum = sum;
.........}
.........return;
......}
......for (let j = i + 1; j < A.length; j++) {
.........dp(j, sum + A[j], remain - 1);
......}
...}
...for (let i = 0; i < A.length; i++) {
......dp(i, A[i], K - 1);
...}
...return maxNum;
}

console.log(solution([4, 9, 8, 2, 6], 3));
console.log(solution([5, 6, 3, 4, 2], 5));
console.log(solution([7, 7, 7, 7, 7], 1));
console.log(solution([10000], 2));
console.log(solution([2, 3, 3, 5, 5], 3));

[Jrue0011]

@guyeu 不用考虑负数吧，题目说都是正数
@Biggoldfish 我也是这个想法，不过和是奇数只考虑到了替换掉最小的奇数，忘了还能换偶数这回事。。。

[fancy111]

最多中级题。
先从大到小排序，找出前 K 个偶数，如果有就相加 return 结果，如果没有或者少于 K 个，就把最大的奇数加进来。
特殊情况返回-1 或者全和。
如果要其他骚操作，也可以加入数据结构。

[noogler67]

定义一种数据结构，要么存一个偶数，要么存两个奇数。然后把奇数从大到小排列转成这种数据结构。然后把所有这种数据结构根据平均数排序。
然后取前 k 个数，如果第 k 个数只能取到一个奇数，就取下一个偶数。

[techme]

@Biggoldfish
这个解法妙啊

[techme]

@rabbbit 这个递归解法挺好，学习了，感谢

[lenqu]

@Biggoldfish 比动态规划好

[daozhihun]

lz 是面试的 ms 嘛

[cloudzhou]

最后和是偶数，那么 偶数 = n 个偶数 + m 个奇数 ，其中个数 m 是偶数，m + n = k，k 是总个数。
要求最大值，将数组分成 偶数数组，奇数数组，从大到小排序。
如果 k 是奇数，k-1 个最大偶数，1 最大奇数，就是答案。
如果 k 是偶数，首先选取 n = k，然后记录总和；
L: 然后 n-2，剔除最后 2 个偶数，加上前 2 个奇数，在算一下总和和之前对比(如果这两奇数和小于提出的两偶数和，直接可以 break)；
重复 L，知道偶数数组或者奇数数组为空，不断比较最大的和

[cloudzhou]

上面 偶数数组，奇数数组，比较就是两个起始 index i, j，一个左移，一个右移，不断逼近的结果，最后得到 i, j

[nznd]

楼上那些解法妙啊，学习到了

[islxyqwe]

按奇偶分组，然后分别排序。如果偶数的前两个和比奇数的前两个和大，从偶数提取两个；否则从奇数提取两个。（有一方个数不足 2 个时，只从另一方提取）
还需取的数不足两个时如果还需提取 1 个就从偶数提取一个，不能提就返回-1

[islxyqwe]

不对，不能处理[20,18,5,3] k=3 的情况，不太行

[ncabhd]

@Biggoldfish #3 这个解法是对的，在优化就是分奇偶两数组排序查找，从时间复杂度上来讲，差别不是很大
@techme 贴的代码有个小问题全选没有验证奇偶；还有个可以优化的地方是数组已经是有序，C#的 Any 的实现不是很清楚，我暂且认为是扫描整个数组，这个是没有必要的。
@rabbbit #5 @techme 这个应该不能算是 DP，应该是 DFS，将所有情况全部列出来，时间复杂度已经涉及到阶乘了
@cloudzhou #13 如果 K 是奇数，k-1 最大偶数和 1 最大奇数答案是奇数的。而且这个也要按照 L 去计算。

[rabbbit]

@ncabhd
嗯,写完了才发现时间复杂度太大了,如果体里的 k 比较小可能还能接受.
对于这道题来数暴力递归应该是不能接受的.

[rabbbit]

嗯,写完了才发现时间复杂度太大了,如果题里的 k 比较小可能还能接受.
对于这道题来说暴力递归应该是不能接受的.

[cloudzhou]

@Biggoldfish 的算法，直观上有问题，但是我验证不出来
@ncabhd 是的，我后面想到了
为了确保正确，我写了代码，你们需要的话，我们来验证一下：
https://gist.github.com/cloudzhou/614d3acf70cbe08a616d0be9888e739e

[cloudzhou]

里面已经有了测试用例，如果你们有新的测试用例，可以加进去，这样很容易验证是否正确
复杂度来说，最大在于排序，所以是 lgn，我的代码，以便于阅读理解为主，所以不考虑极致性能

[LYEHIZRF]

top K 问题 一律堆排序

[finalwave]

分成奇偶两个队列构造最大堆取 pair，K 为奇数时保证偶数堆取走 pair 后还有数就行，O(n+klgn)

[yazoox]

@techme 看你的截图，你是用的 vscode? 为什么你右侧的那一栏，看起来和我的不一样？有什么插件加载改造过了么？

[wang247]

动态规划？

[qwertyegg]

@techme 不要排序啊，最好都是 O(nlogn)。直接扫一遍，把最大的(奇奇偶)和(偶偶偶)扫出来即可

[Biggoldfish]

@ncabhd
在时间复杂度上想要降低的话，可以不必对整个数组排序，利用 quick select algorithm 可以在平均 O(N) 的时间内找到 top K elements，从而我的整个解法可以在 O(N) 完成。不过个人觉得一般笔试应该没人卡这个 logN 。

@cloudzhou
只要证明 1. 如果有偶数和一定可以找到 2. 找到的偶数和一定最大 即可。如果有问题的话找个反例就行。我随便写了一下，LZ 的 test case 都能过 https://leetcode.com/playground/WtagcCkG

@yazoox
LZ 那个界面是 Visual Studio

[noxe]

先排序，找出最大的 k 个值（ k<n 时结果为-1 ）

如果和是偶数，那么就取这 k 个值。
否则只有 2 种情况来改变奇偶性：
1. 用其它值中最大的奇数，替换当前 k 个值中最小的偶数
2. 用其它值中最大的偶数，替换当前 k 个值中最小的奇数

如果无法替换，那么为-1

[noxe]

才发现前面大牛已经说过这思路了，抱歉抱歉😞

[techme]

@daozhihun 是 FNC 一家做财务软件的
@yazoox 我的是 vs2019，vsc 里面也可以打开这个 view 里面有个 showminimap

[MorningStar0]

写在这了，思路大概是堆排序

[MorningStar0]

https://ashes-born.com/2020/05/26/algorithm/%E6%95%B0%E7%BB%84%E4%B8%ADk%E4%B8%AA%E6%95%B0%E7%9A%84%E6%9C%80%E5%A4%A7%E5%81%B6%E6%95%B0%E5%92%8C/

[xmoiduts]

反馈： 某海外通信公司 机试题。也是这个平台也是第三题。