DrawBridge最新OA

分享一个今天刚做的DrawBridge OA，60min 两道题，和之前地里面经给的都不一样。

您好！
本帖隐藏的内容需要积分高于 180 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 180 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

最后，求点大米！

ob123 发表于 2018-8-17 01:29
二分mindiff？能详细解析下吗

把题目描述改写一下：找到最小的k，使得从数组中任意取m个数，这m个数里的最小diff均<=k。很明显这个k满足单调性：即对于k1<k2，如果minDiff均<=k1，那么minDiff必定也都<=k2。
那么就可以二分这个k，转换成这样一个问题：给定k，能否在数组里取m个数，这m个数的最小diff>k。如果可以的话，说明k不是个合法的解，需要变大；否则k合法，可以缩小范围。
具体的判断方法可以通过贪心的方法构造，对于有序数组，先取最小的数，然后往后扫描。每当当前元素与上一次取的元素差>=k时，就取这个元素。如果最后能取超过m个，说明可以取到m个数，这m个数的minDiff>k。
举个例子：a = 1, 2, 3, 5; m = 3; k = 1
先取1;
扫描到3时3 - 1 = 2 > 1,取3;
扫描到5时5 - 3 = 2 > 1,取5.
此时发现已经取了m=3个数了，说明可以取到m个数，这m个数的minDiff > k = 1。
k = 1不满足条件，继续二分。
这样一次判定的时间复杂度是O(N)的，二分复杂度是O(log(Answer))的，总时间复杂度是O(Nlog(Answer))。
思路可以参考蠡口气气死

求问一下第二题思路。。

请问他家是投了就给OA吗？

第二题lz咋做的？

第二题可以这么做：二分这个mindiff,转换成判定在minDiff的限制下能不能在数组里取m个数的问题。可以先对数组排序，从最小的数开始取，每隔mindiff取一个数，最后看能不能取到m个。复杂度O(Nlog(minDiff))

tinylic 发表于 2018-8-14 10:11
第二题可以这么做：二分这个mindiff,转换成判定在minDiff的限制下能不能在数组里取m个数的问题。可以先对数 ...

求详细解释一下～

tinylic 发表于 2018-8-14 10:11
第二题可以这么做：二分这个mindiff,转换成判定在minDiff的限制下能不能在数组里取m个数的问题。可以先对数 ...

二分mindiff？能详细解析下吗