查找与那些相隔最远的海誓山盟要素子集 [英] Find subset with elements that are furthest apart from eachother

问题描述

我有一个面试问题，我似乎无法弄清楚。给定大小为N的阵列，找到大小为k的子集，使得在该子集中的元素是彼此分离最远。换句话说，最大化的元素之间的最小距离成对。

I have an interview question that I can't seem to figure out. Given an array of size N, find the subset of size k such that the elements in the subset are the furthest apart from each other. In other words, maximize the minimum pairwise distance between the elements.

Example:

Array = [1,2,6,10]
k = 3

answer = [1,6,10]

在暴力破解的方式需要找到大小为k的所有子集是指数的运行。

The bruteforce way requires finding all subsets of size k which is exponential in runtime.

我有一个想法是采取从阵列均匀分布的值。我的意思是

One idea I had was to take values evenly spaced from the array. What I mean by this is

1. 在采取第1个和最后一个元素
2. 找到它们之间的差（在这种情况下，10-1），并分割为k（（10-1）/ 3 = 3）
3. 将2球向内两端，挑选出那些+/- 3从previous挑元素。所以在这种情况下，从1至10就找到最接近元素4和7这将是6。

这是基于这样的因素应尽可能均匀s ^ $ P $垫尽可能的直觉。我不知道如何来证明它的工作原理/无法正常工作。如果有人知道如何或有更好的算法请大家分享。谢谢！

This is based on the intuition that the elements should be as evenly spread as possible. I have no idea how to prove it works/doesn't work. If anyone knows how or has a better algorithm please do share. Thanks!

推荐答案

这可使用DP多项式时间内解决。

This can be solved in polynomial time using DP.

第一步是，正如你所说，对列表进行排序A.设X [I，J]是从第i个元素的一个选择Ĵ元素的解决方案。

The first step is, as you mentioned, sort the list A. Let X[i,j] be the solution for selecting j elements from first i elements A.

现在，X [i + 1的，J + 1] =最大（最小（X [K，J]，A [i + 1的] -A [K]））超过K＆其中; = I

Now, X[i+1, j+1] = max( min( X[k,j], A[i+1]-A[k] ) ) over k<=i.

我会离开初始化步骤和子步骤记忆为您的工作。

I will leave initialization step and memorization of subset step for you to work on.

在你的榜样（1,2,6,10），它的工作方式如下：

In your example (1,2,6,10) it works the following way:

    1    2   6   10
1   -    -   -    -
2   -    1   5    9
3   -    -   1    4
4   -    -   -    1

这篇关于查找与那些相隔最远的海誓山盟要素子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！