d****n
发帖数: 233 | 1 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 ).
From:
http://careercup.com/question?id=311822 |
k*n
发帖数: 150 | 2 睡不着，上来做一道题再睡吧。。。
英文很差，硬着头皮练，大家莫笑。。。
firstly, brute force is the last option, which will take C(n,k)*k time
Then let's consider a better solution
apparently, sorting the n numbers will help, this will take n*logn time
now name them x1 to xn
in the ideal case, this max-min diff is (xn-x1)/(k-1)
another thing that is determined is x1 and xn must be selected.
let y1 to yk as the sorted selections. so y1=x1, yk=xn.
now consider greedy like method...
from x1, chose next yi where yi is the most appropr
【在 d****n 的大作中提到】
: 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 ).
: From:
: http://careercup.com/question?id=311822
|
m*****g
发帖数: 226 | 3 don't quite understand this solution.
how about this.
for input array[0...n], asking for k (k<=n)
first sort array into sortedArray[0...n]
calculate the difference between adjacent elements, put them in a linked
list List diff;
next build a min heap of the nodes in the linked list
do n-k times
remove the min from the heap, combine with its adjacent elements in the
difference list, then update the min heap
end
this solution should give O(nlgn) time complexity
another thing, x[1] and x[n] not |
d****n
发帖数: 233 | 4 Very cool, thanks kwn.
【在 k*n 的大作中提到】
: 睡不着，上来做一道题再睡吧。。。
: 英文很差，硬着头皮练，大家莫笑。。。
: firstly, brute force is the last option, which will take C(n,k)*k time
: Then let's consider a better solution
: apparently, sorting the n numbers will help, this will take n*logn time
: now name them x1 to xn
: in the ideal case, this max-min diff is (xn-x1)/(k-1)
: another thing that is determined is x1 and xn must be selected.
: let y1 to yk as the sorted selections. so y1=x1, yk=xn.
: now consider greedy like method...
|
x******3
发帖数: 245 | 5 感觉这个是对的， 但是这一步
combine with its adjacent elements in the
difference list, then update the min heap
应该不是O(lgN), 因为在heap中查找不是lgN
linked
in the
【在 m*****g 的大作中提到】
: don't quite understand this solution.
: how about this.
: for input array[0...n], asking for k (k<=n)
: first sort array into sortedArray[0...n]
: calculate the difference between adjacent elements, put them in a linked
: list List diff;
: next build a min heap of the nodes in the linked list
: do n-k times
: remove the min from the heap, combine with its adjacent elements in the
: difference list, then update the min heap
|
x******3
发帖数: 245 | 6 也想了DP的方法，大家多多拍砖
任选k个数， 将其排序，那么两元素最小的delta一定是产生于排序后相邻两元素之间
， 这点和mustang的方法相同
如果将原数组排序， 问题等价于找一个长度为k的子序列，其最小delta在所有长度为k
的子序列中最大
DP 解法
定义 S(i, j) = max of min delta in all subsequences ending at a[j] with
length i
则存在
S(i, j) = max { min{delta(a[j], a[t]), S(i-1, t)} } for all t
用T(i, j)储存计算S(i, j)时用的t， 以后可以用于构造出需要的子序列
例子
[1, 3, 5, 7, 8], choose 4 elements
从左到右，从上到下计算S
j
S 1 2 3 4 5
i= 1 0 0 0 0 0
2 0 2 4 6 7
3 0 0 2 4 3
4 0 0 0 2 2
选取i＝4这一行中最大元素即可，可以存在 |
J*****n
发帖数: 4859 | 7 对sequence取差，然后用Kadane Algo，从头到尾，再从尾到头的各用一遍就可以了。
时间复杂度是线性的。 |
m*****g
发帖数: 226 | 8 这个是图省事
在heap找最小当然O(1)。但是等下update要O(lgn)。
【在 x******3 的大作中提到】
: 感觉这个是对的， 但是这一步
: combine with its adjacent elements in the
: difference list, then update the min heap
: 应该不是O(lgN), 因为在heap中查找不是lgN
:
: linked
: in the
|
x******3
发帖数: 245 | 9 不是很明白，能run个例子吗
【在 J*****n 的大作中提到】
: 对sequence取差，然后用Kadane Algo，从头到尾，再从尾到头的各用一遍就可以了。
: 时间复杂度是线性的。
|
k*n
发帖数: 150 | 10 removing min cannot guarantee best solution.
and for x[0] and x[n]
it's right that it's not necessary to select both of them
but if there is a solution not selecting them, there must be a solution
similar and selecting them.
the
【在 m*****g 的大作中提到】
: don't quite understand this solution.
: how about this.
: for input array[0...n], asking for k (k<=n)
: first sort array into sortedArray[0...n]
: calculate the difference between adjacent elements, put them in a linked
: list List diff;
: next build a min heap of the nodes in the linked list
: do n-k times
: remove the min from the heap, combine with its adjacent elements in the
: difference list, then update the min heap
|
|
|
k*n
发帖数: 150 | 11 不懂，请教一下？
【在 J*****n 的大作中提到】
: 对sequence取差，然后用Kadane Algo，从头到尾，再从尾到头的各用一遍就可以了。
: 时间复杂度是线性的。
|
J*****n
发帖数: 4859 | 12
Kadane算法知道吧，那个是用来求最大连续和的。
你把初始数组相邻的求一个差，再对得到的新数组用Kadane，所得的就是最大的差。
不过Kadane是有顺序的，也就是总是用大下标去减小下标。所以你还要从右往左的在用
一遍。
得到两个最大差（左——〉右，右——〉左），比较一下就可以了。
空间和时间都是线性的，如果你不要原数组了，那空间就是O(1)。
【在 k*n 的大作中提到】
: 不懂，请教一下？
|
k*n
发帖数: 150 | 13 好像有问题，你的k在哪里？
你说的是一系列数里面求最大连续和的算法？
那里面初始数组是无序的而且可正可负的
我觉得你把题理解错了
【在 J*****n 的大作中提到】
:
: Kadane算法知道吧，那个是用来求最大连续和的。
: 你把初始数组相邻的求一个差，再对得到的新数组用Kadane，所得的就是最大的差。
: 不过Kadane是有顺序的，也就是总是用大下标去减小下标。所以你还要从右往左的在用
: 一遍。
: 得到两个最大差（左——〉右，右——〉左），比较一下就可以了。
: 空间和时间都是线性的，如果你不要原数组了，那空间就是O(1)。
|
x******3
发帖数: 245 | 14 同问
【在 k*n 的大作中提到】
: 好像有问题，你的k在哪里？
: 你说的是一系列数里面求最大连续和的算法？
: 那里面初始数组是无序的而且可正可负的
: 我觉得你把题理解错了
|
d****n
发帖数: 233 | 15 I think the optimization in Kwn's solution could have bugs. Here is mine
without any optimization:
int FindSubSeqWithMaxMinDistance(int *X, int N, int K)
{
if ( N < 2 || K < 2 || K > N ) return 0;
// Alloc buffers
int **F = (int **)malloc(K*sizeof(int *)+ K*N*sizeof(int));
int *temp = (int *)(F + K);
for (int i = 0; i < K; i++)
{
F[i] = temp + N*i;
}
memset(temp, 0, K*N*sizeof(int));
for(int j = 0; j < N; j++)
{
F[0][j] = INT_MAX;
}
// Assume A
【在 k*n 的大作中提到】
: 睡不着，上来做一道题再睡吧。。。
: 英文很差，硬着头皮练，大家莫笑。。。
: firstly, brute force is the last option, which will take C(n,k)*k time
: Then let's consider a better solution
: apparently, sorting the n numbers will help, this will take n*logn time
: now name them x1 to xn
: in the ideal case, this max-min diff is (xn-x1)/(k-1)
: another thing that is determined is x1 and xn must be selected.
: let y1 to yk as the sorted selections. so y1=x1, yk=xn.
: now consider greedy like method...
|
a***9
发帖数: 364 | 16 这个复杂度是多少的？ 我在本版56073帖做过，不过也没人搭理
看一眼呗～
【在 d****n 的大作中提到】
: I think the optimization in Kwn's solution could have bugs. Here is mine
: without any optimization:
: int FindSubSeqWithMaxMinDistance(int *X, int N, int K)
: {
: if ( N < 2 || K < 2 || K > N ) return 0;
: // Alloc buffers
: int **F = (int **)malloc(K*sizeof(int *)+ K*N*sizeof(int));
: int *temp = (int *)(F + K);
: for (int i = 0; i < K; i++)
: {
|
l******o
发帖数: 144 | 17 你那个DP显然是对的。我有一个不需要DP的方法，复杂度在O(klgn*lg(x[n]-x[1]))，
和你那个复杂度差不多。
首先，给定一个值d，我用greedy algorithm可以判断这个d是否可能。简单的说就是
i1=1, 找最小的i2使得x[i2]-x[i1]>=d，然后找最小的i3使得x[i3]-x[i2]>=d ……
这个步骤需要k次binary search，所以复杂度是O(klgn)
然后对d进行binary search，需要做O(lg(x[n]-x[1]))次，所以复杂度是O(klgn*lg(x[
n]-x[1]))。
这个复杂度是多少的？ 我在本版56073帖做过，不过也没人搭理
看一眼呗～
【在 a***9 的大作中提到】
: 这个复杂度是多少的？ 我在本版56073帖做过，不过也没人搭理
: 看一眼呗～
|
a***9
发帖数: 364 | 18 哇，这么神奇阿
x[
【在 l******o 的大作中提到】
: 你那个DP显然是对的。我有一个不需要DP的方法，复杂度在O(klgn*lg(x[n]-x[1]))，
: 和你那个复杂度差不多。
: 首先，给定一个值d，我用greedy algorithm可以判断这个d是否可能。简单的说就是
: i1=1, 找最小的i2使得x[i2]-x[i1]>=d，然后找最小的i3使得x[i3]-x[i2]>=d ……
: 这个步骤需要k次binary search，所以复杂度是O(klgn)
: 然后对d进行binary search，需要做O(lg(x[n]-x[1]))次，所以复杂度是O(klgn*lg(x[
: n]-x[1]))。
:
: 这个复杂度是多少的？ 我在本版56073帖做过，不过也没人搭理
: 看一眼呗～
|
g*******y
发帖数: 1930 | 19 你貌似理解错了题目意思？
【在 J*****n 的大作中提到】
:
: Kadane算法知道吧，那个是用来求最大连续和的。
: 你把初始数组相邻的求一个差，再对得到的新数组用Kadane，所得的就是最大的差。
: 不过Kadane是有顺序的，也就是总是用大下标去减小下标。所以你还要从右往左的在用
: 一遍。
: 得到两个最大差（左——〉右，右——〉左），比较一下就可以了。
: 空间和时间都是线性的，如果你不要原数组了，那空间就是O(1)。
|
g*******y
发帖数: 1930 | 20 对，这个方法在x[n]-x[1]不太大的情况下还不错
另外的一个方法就是DP+优化/log加速了，以前讨论过
x[
【在 l******o 的大作中提到】
: 你那个DP显然是对的。我有一个不需要DP的方法，复杂度在O(klgn*lg(x[n]-x[1]))，
: 和你那个复杂度差不多。
: 首先，给定一个值d，我用greedy algorithm可以判断这个d是否可能。简单的说就是
: i1=1, 找最小的i2使得x[i2]-x[i1]>=d，然后找最小的i3使得x[i3]-x[i2]>=d ……
: 这个步骤需要k次binary search，所以复杂度是O(klgn)
: 然后对d进行binary search，需要做O(lg(x[n]-x[1]))次，所以复杂度是O(klgn*lg(x[
: n]-x[1]))。
:
: 这个复杂度是多少的？ 我在本版56073帖做过，不过也没人搭理
: 看一眼呗～
|
d*******e
发帖数: 34 | 21
为k
[1, 3, 5, 7, 8], choose 4 elements
从左到右，从上到下计算S
j
S 1 2 3 4 5
i= 1 0 0 0 0 0
2 0 2 4 6 7
3 0 0 2 4 3
4 0 0 0 2 2
Shouldn't S[3,4] be 2:
1, 3, 7: 2
1, 5, 7: 2
3, 5, 7: 2
Did I miss something?
【在 x******3 的大作中提到】
: 也想了DP的方法，大家多多拍砖
: 任选k个数， 将其排序，那么两元素最小的delta一定是产生于排序后相邻两元素之间
: ， 这点和mustang的方法相同
: 如果将原数组排序， 问题等价于找一个长度为k的子序列，其最小delta在所有长度为k
: 的子序列中最大
: DP 解法
: 定义 S(i, j) = max of min delta in all subsequences ending at a[j] with
: length i
: 则存在
: S(i, j) = max { min{delta(a[j], a[t]), S(i-1, t)} } for all t
|
