0

我有一个编程问题，可以描述如下：

给定一个排序数组 x 和一个数字 k，我被要求返回另一个排序数组 y，这样数组 y 中的元素按其 VALUE（而不是索引）均匀分布。

我需要编写一个算法来解决这个问题。

这个问题应该表述如下：

\max_{x\in y}{\min_{a,b\in x}{|a-b|}}

例如，

  • x=[1,2,4,8,16,32,64,128] 和 k=3，我应该有 y=[1,64,128]
  • x=[1,2,4,8,16,32,64,128] 和 k=5，我应该有 y=[1,16,32,64,128]
  • x=[1,2,3,4,5,6,7] 和 k=4，我应该有 y=[1,3,5,7]

谢谢。

好的，我想我已经找到了解决方案。这个想法是

  1. 我们从 x 中选择两个末端元素并添加到 y；
  2. 我们将这两个端点的步长计算为 (x[-1]-x[0])/k-1;
  3. 我们从 x 中删除任何小于 x[0]+step 的元素，以及从 x 中删除大于 x[-1]-step 的元素；
  4. k=k-2；
  5. 如果k==0，终止算法；如果k==1，求中间元素；

代码是

def sample_element_even(idx, k, val=None):
"""
this function returns k elements from idx (which is a list), such that the samples's value (val) are evenly
distributed
note idx should be sorted. If idx is comparable, val will be used instead
"""
if val is None:
    val=idx
# number of element remains
m=k
n=len(idx)
left=0
right=n-1
# all elements found
if m==0:
    return []
# special case
if m==1:
    middle=bisect.bisect(val, (val[left]+val[right])/2.0)
    if val[middle]+val[middle-1]>val[left]+val[right]:
        result=[idx[middle-1]]
    else:
        result=[idx[middle]]
    return result
# normal case
result=[None]*k
while m>0:
    # normal case
    # pick the two ends first
    result[(k-m)/2]=idx[left]
    result[k-1-(k-m)/2]=idx[right]
    # compute the step
    step=(val[right]-val[left])/(m-1.0)
    m=m-2
    # all elements found
    if m==0:
        break
    # only one elements left, choose its middle
    if m==1:
        middle=bisect.bisect(val, (val[left]+val[right])/2.0)
        if val[middle]+val[middle-1]>val[left]+val[right]:
            result[(k-m)/2]=idx[middle-1]
        else:
            result[(k-m)/2]=idx[middle]
        break
    left=bisect.bisect(val, val[left]+step)
    right=bisect.bisect(val, val[right]-step)
return result
4

0 回答 0