r******g
发帖数: 58 | 1 在careercup上面看到的。觉得还蛮有意思。
不知道有没有 nlogn 的解法。
大家讨论一下吧。
Given an array of 'n' random integers. Given an integer 1<=n. Find the k
numbers such that the minimum difference of all the possible pairs of k
numbers is maximum (maximum among other minimum differences for various
possible selections of k numbers ). | g*******y
发帖数: 1930 | 2 讨论过了吧，普通动态规划n×n×k, 加速后nklogn
【在 r******g 的大作中提到】
: 在careercup上面看到的。觉得还蛮有意思。
: 不知道有没有 nlogn 的解法。
: 大家讨论一下吧。
: Given an array of 'n' random integers. Given an integer 1<=n. Find the k
: numbers such that the minimum difference of all the possible pairs of k
: numbers is maximum (maximum among other minimum differences for various
: possible selections of k numbers ).
| r******g
发帖数: 58 | 3
可以稍微解释一下吗？这个是个一维数组,为什么需要n*n啊？
这个题目的讨论大概在干什么时候啊？我自己可以去翻翻原来的老贴。谢谢大牛。
【在 g*******y 的大作中提到】
: 讨论过了吧，普通动态规划n×n×k, 加速后nklogn
| x****r
发帖数: 99 | 4 同问啊，，完全没思路
【在 g*******y 的大作中提到】
: 讨论过了吧，普通动态规划n×n×k, 加速后nklogn
| K******g
发帖数: 1870 | | r******g
发帖数: 58 | | a***9
发帖数: 364 | 7 是不是这样：
1. sort 这 n个数，记结果为a_1,...,a_n （O(nlogn));
2. 记 D(i,j) （i= 1 to n, j= 1 to min(i,k)) 为必须包括第i个数的前i个数中
取j个使得两两最小差值最大的那个差值，方程为：
D(i,j) = max{min(D(s, j-1), a_i-a_s) (j-1<= s <= i-1)}
算这个D(i,j)直接做是O(n)，但可以加速, 因为(a_i-a_s)值关于s是non-increasing的，
而D(s,j-1)值关于s是non-decreasing的,所以可以做binary search:
search (int start, int end,int i, int j) {
if (start >= end) return;
mid = (start+end)/2
if D(mid,j-1) > a_i - a_mid
then search (start, mid, i, j)
else search (mid, end, i,j)
}
所以第二步最后复杂度O(n
【在 g*******y 的大作中提到】
: 讨论过了吧，普通动态规划n×n×k, 加速后nklogn
|
|
