如何从长度为“n”的数组中删除等距元素以匹配给定长度“y”？

Question

假设我有数组foo和一个正整数y，其中foo.length> y。我想从中删除元素，foo以便foo.length成为y（或非常接近它）。

另外，我需要保留 的第一个和最后一个元素foo。被删除元素的索引必须尽可能均匀地间隔开。 Foo可以被切片，或者可以用来创建一个新数组。

示例：如果foo=[a,b,c,d,e,f,g,1,2,3,4,5]和y= 6，则trimmedfoo可能是[a,c,e,g,2,4,5]或 可能[a,c,e,2,4,5]，但不是[a,c,e,g,2,4]因为 的最后一个元素foo丢失。

伪代码解决方案很好，尽管 as3 是我选择的语言。:)

谢谢！

Answer 1

假设您有一个长度为 的字符串n，并且您希望它的长度为m。您可以n-2从中选择元素，也m-2可以为新数组选择元素。现在，假设您当前已选择i元素并已传递j元素。如果i/j<(m-2)/(n-2)那么你就落后了。你可能应该采取另一个元素。对于最大均匀的选择，您真正想知道的是是否(i+1)/(j+1)或i/(j+1)更接近您的目标(m-2)/(n-2)。如果溢出不是问题，您可以做一些代数来弄清楚这相当于(i+1)*(n-2) - (j+1)*(m-2)是大于还是小于(n-2)/2；手段i越多越好（所以不要采用这个），而手段越少越好i+1。

我不熟悉 ActionScript，但这里有一些 Scala 希望可以作为伪代码工作：

// Don't worry about the [T: ClassManifest] thing
// that just means it can work on arrays of any type

def pare[T: ClassManifest](a: Array[T], m: Int) = {
  val b = new Array[T](m)
  val n2 = a.length - 2
  val m2 = m - 2
  b(0) = a(0)
  var i,j = 0
  while (j < n2) {
    val diff = (i+1)*n2 - (j+1)*m2
    if (diff < n2/2) {
      i += 1
      j += 1
      b(i) = a(j)
   }
   else j += 1
  }
  b(m2+1) = a(n2+1)
  b    // This means "return b"
}

我们来尝试一下吧！

scala> pare(Array[Any]('a','b','c','d','e','f','g',1,2,3,4,5),6)   
res1: Array[Any] = Array(a, c, e, 1, 3, 5)

scala> pare(Array(1,2,3,4,5,6,7,8,9),4)
res2: Array[Int] = Array(1, 4, 7, 9)

scala> pare(('a' to 'z').toArray, 16)
res3: Array[Char] = Array(a, b, d, f, h, i, k, m, n, p, r, t, u, w, y, z)

正如您所看到的，这提供了非常均匀的间距。