Как написать функцию, которая изменяет массив с числами относительно самых высоких в нем?

Question

[rd100]

Есть массив, который нужно перебрать так, чтобы узнать количество незаполненных элементов
Например 0 - незаполненный, 1, 2 и т.д. заполненные
Есть массив [0, 2, 1, 0, 0, 0, 0, 2, 0, 0, 0]
Каждая цифра в нем заполняет рядом с собой стоящие на ее количество и делает их заполненными автоматический
Например этот массив должен уже выглядеть, как [-1, 2, -1, -1, 0, -1, -1, 2, -1, -1, 0]
То есть

[0, 1, 0] => [-1, 1, -1]
[0, 2, 0, 0, 0] => [-1, 2, -1, -1, 0]
[2, 1, 0, 0, 0] => [2, -1, -1, 0, 0]
[2, 0, 1, 0, 0] => [2, -1, 1, -1, 0]

Где, если пересекается 2 и 1, он превратит 1 в -1, если 1 не закрывает рядом стоящий 0, который превратит в -1.
В итоге нам нужно получить количество всех цифр, которые не равны -1

Comments

[Alexandroppolus]

1, 2 и т.д.

но ведь не только 1 и 2, могут быть и большие, сравнимые с длиной массива?

Где, если пересекается 2 и 1, он превратит 1 в -1,

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

[rd100]

Alexandroppolus, да, если высшее перекрывает низшее, которое не перекрывает дальше, чем то высшее, то оно становится -1, т.к. то высшее их всех перекрывает

Answer 1

[Олег Барабанов]

Мой грубый и неаккуратный пример, если я конечно правильно понял, что требуется. Смотреть на codepen

function transformArray(sourceArray) {
  const arr = sourceArray.slice(0);
  for (let max = Math.max(...arr); max > 0; max--) {
    for (let i = 0; i < arr.length; i++) {
      if (arr[i] === max) {
        const startRange = Math.max(0, i - max);
        const endRange = Math.min(arr.length - 1, i + max);
        for (let i2 = startRange; i2 <= endRange; i2++) {
          if (arr[i2] >= max) continue;
          if (startRange > Math.max(0, i2 - arr[i2])) continue;
          if (endRange < Math.min(arr.length - 1, i2 + arr[i2])) continue;
          arr[i2] = -1;
        }
      }
    }
  }
  return arr;
}

Answer 2

[Михаил Ушенин]

Так вроде должно работать:

function process (source) {
    const result = source.slice(0);
    const count = result.length;

    result.forEach((n, i) => {
        if (n > 0) {
            const min = Math.max(i - n, 0);
            const max = Math.min(i + n, count - 1);

            for (let c = min; c <= max; c++) {
                let check = result[c];

                if (check < 1 || (check < n && c - check >= min && c + check <= max)) {
                    result[c] = -1;
                }
            }
        }
    });

    return result;
}

Answer 3

[Alexandroppolus]

Вариант "туда и обратно", работающий за время O(N) и без вспомогательной памяти

function processDirection(arr, first, end, step) {
    let top = -1;
    for (let i = first; i !== end; i += step) {
        const value = arr[i];
        if (value <= top) {
            arr[i] = -1;
        } else {
            top = value;
        }
        top--;
    }
}

function updateArray(arr) {
    processDirection(arr, 0, arr.length, 1);
    processDirection(arr, arr.length - 1, -1, -1);
    return arr;
}

// --------
updateArray([5, 1, 1, 0, 2, 1, 1, 0]); // [5, -1, -1, -1, 2, -1, 1, -1]

Еще вопрос по условию. На массиве [2, 1, 1, 1] результат получается [2, -1, 1, 1].
Предпоследняя единица выживает, потому что она "смотрит дальше", чем двойка. Но эта единица не обращает ни одного нуля (нет нулей, которые она могла бы переделать в -1).
Как надобно понимать условие? Оставлять 1, или менять на -1?
Другие решения дают тот же результат.

Comments

[Олег Барабанов]

updateArray([1, 0, 2, 0, 0 ,3 , 1, 2, 1]); // => [1, -1, 2, -1, -1, 3, -1, 2, -1]

Хмм..., а разве тут не должно быть [-1, -1, 2, -1, -1, 3, -1, -1, -1] ? Хотя не исключаю, что я чего-то в логике вопроса не уловил...

[Alexandroppolus]

Олег Барабанов, вот это тоже вопрос к автору. Первая единица и последняя двойка выживают, потому что формально они слишком далеко от более крупных чисел. Но влияние этих крупных чисел простирается до границ массива, и с этой точки зрения выжившие бесполезны.

но по такой логике для [2, 1, 1, 1] должно быть [2, -1, 1, -1] - предпоследняя единица достает до края, и потому последняя должна уйти в минус как бесполезная...

в общем, формулировка условия пока размытая.

[Alexandroppolus]

по такой логике для [2, 1, 1, 1] должно быть [2, -1, 1, -1] - предпоследняя единица достает до края, и потому последняя должна уйти в минус как бесполезная...

Не, по идее так быть не должно. Числа одного размера не могут минусить друг друга.

Исправленный вариант:

function processDirection(arr, first, end, step) {
    let top = -1;
    let max = -1;
    for (let i = first; i !== end; i += step) {
        const value = arr[i];
        if (value <= top || (max > value && Math.abs(i - end) <= top + 1)) {
            arr[i] = -1;
        } else {
            max = top = value;
        }
        top--;
    }
}

function updateArray(arr) {
    processDirection(arr, 0, arr.length, 1);
    processDirection(arr, arr.length - 1, -1, -1);
    return arr;
}