Как удалить одинаково расположенные элементы из массива с длиной 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 <<code>(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;more означает i лучше (так что не берите этот), а less означает 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)

Как видите, это дает очень равномерные расстояния.

Answer 2

Я перевел потрясающий алгоритм Рекса Керра на PHP и хотел опубликовать его здесь, так как думаю, что другим будет легче его читать.Единственная реальная разница в том, что это возвращает массив нетронутым, если он меньше требуемого количества:

private function evenlyReduceArray($originalArray, $desiredCount){

    if(count($originalArray) <= $desiredCount)
    {
        return $originalArray;
    }

    $newArray             = array();
    $trimmedLength        = count($originalArray) - 2;
    $trimmedDesiredCount  = $desiredCount - 2;

    $newArray[0] = $originalArray[0];

    $i = 0;
    $j = 0;
    while($j < $trimmedLength)
    {
        $diff = ($i + 1) * $trimmedLength - ($j + 1) * $trimmedDesiredCount;
        if($diff < $trimmedLength / 2)
        {
            $i += 1;
            $j += 1;
            $newArray[$i] = $originalArray[$j];
        }
        else{
            $j+= 1;
        }
    }

    $newArray[$trimmedDesiredCount + 1] = $originalArray[$trimmedLength + 1];

    return $newArray;
}

Answer 3

вычтите значение y из длины foo.разделите длину foo с результатом вычитания - и позвольте вызвать результат N. Теперь скопируйте массив в новый массив и перепрыгните без копирования каждого N-го элемента.убедитесь, что вы начинаете перепрыгивать через элементы только со второго элемента и останавливаетесь перед последним (если последний N-й счет является последним элементом, просто перепрыгните через предыдущий).

в приведенном выше примере:foo.length = 12, y = 6, N = 12-6 = 6, foo.length / N = 2

, поэтому мы переходим и перемещаем каждый второй элемент.

в другом примеренам может потребоваться перепрыгнуть еще несколько элементов, чтобы исправить результирующий массив деления с остатком

Answer 4

Проверено против ваших ценностей и других и работает.

var originalArray:Array = ['a','b','c','d','e','f','g','1','2','3','4','5'];
var newLength:Number = 6;

var trimmedArray:Array = originalArray.filter(function(item:*, i:int, a:Array):Boolean {
    return  (((i + 1) % (a.length/newLength)) == 1) || (i == 0) || (i == a.length - 1);
});

trace(trimmedArray); // outputs a,c,e,g,2,4,5

Answer 5

Если первый и последний элементы являются единственными неприкасаемыми элементами в массиве, не будет ли более простой способ неоднократно удалять второй и второй последние элементы до тех пор, пока вы не достигнете нужной длины?foo должно быть [a, e, f, g, 1,5];