w*****k
发帖数: 20 | 1 考古得到一个今年的google面试题(dawenxi88):已知一个长度为n的数组。假设一个子
集有k个数，则我们有k(k-1)/2个pair(x,y)。定义pair difference为|x-y|，子集的半
径为最小的pair difference。现在要求长度为k的半径最大的子集。原题在
http://www.mitbbs.com/article/JobHunting/31540541_3.html
大家讨论了很多，基本思路是DP。如果要求从A[i,j]中选k个数，则一定是从A[i,m]中
选p个数，A[i,m]中选k-p 个数，遍历所有的m和p，求一个最大值，就可以完成DP的一
步。这个命题看似正确，但是经不住推敲,因为这样组合起来不一定是半径最大的长度
为k的子集。假设
A[] = {0, 25, 49, 51, 75, 100 }
k= 4,p=2.
则{0, 25, 49}的半径最大子集是{0,49},{51, 75, 100 }的半径最大子集是{51,100 }
，但是{0, 25, 49, 51, 75, 100 }的最大半径子集显然不是{0, 49, 51, 100 | s****a
发帖数: 528 | 2 if given k number, find the minimum |x-y|
sort first, minimum distance = minimum difference of two neighbor numbers
a(i,j) choose K, I think we should also sort first and do DP | h**6
发帖数: 4160 | 3 这种题，可以二分的。
把数组排序后，找出最大值和最小值之差。然后在这个范围内判断，是否存在pair
distance至少为d的子集，存在则增加d，不存在则减小d。 | s****a
发帖数: 528 | 4 If now we have N numbers, and we want to choose k number with minimum radius
. P(N, k) on array A
sort the N numbers, the minimum distance is |Aj-Aj+1|, we know
either Aj or A(j+1) must not be in the k number
so the problem becomes P(N-1, k) on array without Aj, or without Aj+1 | l******e
发帖数: 12192 | 5 应该是从A[i,m]中选p个数，A[m,j]中选k-p+1个数
A[i], A[m], A[j]必然被选中
【在 w*****k 的大作中提到】
: 考古得到一个今年的google面试题(dawenxi88):已知一个长度为n的数组。假设一个子
: 集有k个数，则我们有k(k-1)/2个pair(x,y)。定义pair difference为|x-y|，子集的半
: 径为最小的pair difference。现在要求长度为k的半径最大的子集。原题在
: http://www.mitbbs.com/article/JobHunting/31540541_3.html
: 大家讨论了很多，基本思路是DP。如果要求从A[i,j]中选k个数，则一定是从A[i,m]中
: 选p个数，A[i,m]中选k-p 个数，遍历所有的m和p，求一个最大值，就可以完成DP的一
: 步。这个命题看似正确，但是经不住推敲,因为这样组合起来不一定是半径最大的长度
: 为k的子集。假设
: A[] = {0, 25, 49, 51, 75, 100 }
: k= 4,p=2.
| t****a
发帖数: 1212 | 6 I think that is the right solution.
【在 l******e 的大作中提到】
: 应该是从A[i,m]中选p个数，A[m,j]中选k-p+1个数
: A[i], A[m], A[j]必然被选中
| h**6
发帖数: 4160 | 7 可以化简一下：
A[i,m]中选2个数，A[m,j]中选k-1个数
A[i], A[m], A[j]必然被选中
【在 l******e 的大作中提到】
: 应该是从A[i,m]中选p个数，A[m,j]中选k-p+1个数
: A[i], A[m], A[j]必然被选中
| t*****j
发帖数: 1105 | 8 同意这个思路，总的distance就是两个distance的min。
【在 l******e 的大作中提到】
: 应该是从A[i,m]中选p个数，A[m,j]中选k-p+1个数
: A[i], A[m], A[j]必然被选中
| s****a
发帖数: 528 | 9 这样和 brutal force 有区别吗？
【在 t*****j 的大作中提到】
: 同意这个思路，总的distance就是两个distance的min。
| h**k
发帖数: 3368 | 10 brutal force 是exponecial的。
DP是O(kn)的
【在 s****a 的大作中提到】
: 这样和 brutal force 有区别吗？
| B***n
发帖数: 84 | 11 这里的m是任意的都可以吗？还是得遍历所有的m？
比如例子
A[] = {0, 25, 49, 51, 74, 96 }
选m=3的话就有问题
在A[1,3]={0,25,49}选2个数，即{0，49}， d=49
在A[3,6]={49,51,74,96}选k-1=3个数，即{49，74，96}, d=22
合并起来就是 {0，49，74，96}，d=22
然而最大子集应该是{0,25,49,96}, d=24
不知道理解的对否？谢谢
【在 h**6 的大作中提到】
: 可以化简一下：
: A[i,m]中选2个数，A[m,j]中选k-1个数
: A[i], A[m], A[j]必然被选中
| h**6
发帖数: 4160 | 12 必须遍历所有的m，然后取最大值。
同楼上larrabee的算法相比，我省略了 p 这个参数。
【在 B***n 的大作中提到】
: 这里的m是任意的都可以吗？还是得遍历所有的m？
: 比如例子
: A[] = {0, 25, 49, 51, 74, 96 }
: 选m=3的话就有问题
: 在A[1,3]={0,25,49}选2个数，即{0，49}， d=49
: 在A[3,6]={49,51,74,96}选k-1=3个数，即{49，74，96}, d=22
: 合并起来就是 {0，49，74，96}，d=22
: 然而最大子集应该是{0,25,49,96}, d=24
: 不知道理解的对否？谢谢
| A*********r
发帖数: 564 | 13 为了这道题，专门复习了一下dp,并且把两个帖子的回复都仔细研读了一遍，现在来总
结一下吧。
原题：给定M个数字的从1到N的整数数组，找出一个大小为K的子集，这个子集
的半径定义为最小的pair Distance，让找出最大半径的这样的子集。
首先说如果是brute force, 要从M个数中选出K个数，然后计算每个K子集的半径，找到
最大的那个，复杂度为 C(M,K), 算是exponential的了。。
然后很显然这是个optimization problem (maximize the radius),所以可以考虑用DP.
用DP的最重要的就是找到如何从已知的optimal subproblem, 推导出当前的optimal
state. 对于这个题，就是如何从已知的optimal (K-1)元素的子集的， 得到含有K元素
的optimal的子集。
在回复很多人都知道这一点，如果没有特殊的约束条件，这两个子集可以完全不一样，
也构不成DP中的subproblem了。所以我们要先sort输入数组，这样保证了每一个pair
distance involving i and previo
【在 w*****k 的大作中提到】
: 考古得到一个今年的google面试题(dawenxi88):已知一个长度为n的数组。假设一个子
: 集有k个数，则我们有k(k-1)/2个pair(x,y)。定义pair difference为|x-y|，子集的半
: 径为最小的pair difference。现在要求长度为k的半径最大的子集。原题在
: http://www.mitbbs.com/article/JobHunting/31540541_3.html
: 大家讨论了很多，基本思路是DP。如果要求从A[i,j]中选k个数，则一定是从A[i,m]中
: 选p个数，A[i,m]中选k-p 个数，遍历所有的m和p，求一个最大值，就可以完成DP的一
: 步。这个命题看似正确，但是经不住推敲,因为这样组合起来不一定是半径最大的长度
: 为k的子集。假设
: A[] = {0, 25, 49, 51, 75, 100 }
: k= 4,p=2.
|
|
