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

[techme]

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

[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]

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