Неотрицательное множество вычитания

Question

Это применимо к любому языку, но я бы реализовал его в узле.

У меня есть набор целых чисел и значение, которое мне нужно вычесть из суммы набора.

[4, 5, 6, 7, 8] - 25

Если мы вычтем из каждого числа равномерно, мы получим:

[-1, 0, 1, 2, 3]

Однако я не хочу, чтобы числа были меньше 0. Итак, если бы я писал алгоритм длясделать это, отрицательные числа будут в равной степени перетекать в оставшиеся числа, и теперь у нас будет:

[0, 0, 1, 2, 3] - 1

Создание результирующего набора:

[0, 0, 1 - 0.333, 2 - 0.333, 3 - 0.333]

Есть ли быстрая операция илисерия операций, которые не включают в себя циклы до завершения для решения этой проблемы?

Обратите внимание, что это именно тот результат, который я хочу.Все отрицательные значения переполняются ДАЖЕ в оставшиеся положительные значения.

Я использую Lodash, поэтому ответ в Lodash будет приемлемым.

Answer 1

Не требуется сортировка, но с использованием рекурсии.

let output = substract( [6,5,7,4,8], 25, 5)
console.log(output)
output = substract( [6,5,7,4,8.5], .10, 5)
console.log(output)
function substract(array, substractThis, length) {
	let delta = substractThis/length;
	let toSubstract;
	let out = array.map(ele => {
		toSubstract =  Math.min(ele, delta);
		substractThis -= toSubstract;
		ele = ele - toSubstract;
		length -= !ele;
		return ele;
	});
	if(substractThis < 1) {
		return out
	}
	return substract(out, substractThis, length)
}

Answer 2

Для упорядоченного массива можно использовать подход с одним циклом и посмотреть на изменяющееся значение дисперсии.

function subtract(array, delta) {
    return array.map((v, i, { length }) => {
        var d = delta / (length - i);
        delta -= Math.min(v, d);
        return Math.max(0, v - d);
    });
}

console.log(subtract([4, 5, 6, 7, 8], 25));

Answer 3

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

const spreadSubtract = (arr, val) =>
{
    // Get the numbers of positive (> 0) elements on the array.

    let len = arr.filter(x => x > 0).length;

    // Get the new subtract value.

    let sub = val / len;

    // Stop condition: if the positive (> 0) elements on the
    // array minus the subtract value are all positive (> 0),
    // then return the mapped array.

    if (!arr.some(x => x > 0 && x - sub < 0))
    {
        return arr.map(x => x > 0 ? x - sub : x);
    }
    
    // Get the minimum element on the array that will be
    // negative when subtracting <sub> from it.

    sub = Math.min(...arr.filter(x => x > 0 && x - sub < 0));

    // Proceed to next iteration of the recursion.

    return spreadSubtract(
        arr.map(x => x > 0 ? x - sub : x),
        val - sub * len
    );
}

// OP example:
console.log(spreadSubtract([4, 5, 6, 7, 8], 25));

// Another test:
console.log(spreadSubtract([0, 9, 1, 5, 3], 11));

// Test subtract greater than the sum of array values:
console.log(spreadSubtract([4, 0, 1, 2, 5], 20));

.as-console {background-color:black !important; color:lime;}
.as-console-wrapper {max-height:100% !important; top:0;}

А вот один из подходов, который вы можете использовать, когда массив сортируется в порядке возрастания:

const spreadSubtract = (arr, val) =>
{
    let avgSub = val / arr.length;

    return arr.map((x, idx) =>
    {
        if (x < avgSub)
        {
            avgSub = (val -= x) / (arr.length - idx - 1);
            return 0;
        }
        else
        {
            return x - avgSub;
        }
    });
}

// Tests
let test1 = [[4, 5, 6, 7, 8], 25];
let test2 = [[0, 9, 1, 5, 3], 11];
let test3 = [[4, 0, 1, 2, 5], 20];

// Note array are sorted first.
console.log(spreadSubtract(test1[0], test1[1]));
console.log(spreadSubtract(test2[0].sort(), test2[1]));
console.log(spreadSubtract(test3[0].sort(), test3[1]));

.as-console {background-color:black !important; color:lime;}
.as-console-wrapper {max-height:100% !important; top:0;}

Answer 4

Вы можете уменьшить количество необходимых циклов, предполагая, что установленное число

1. имеет только положительные значения
2. Сумма набора больше, чем значение, которое нужно вычесть
3. Это может быть отсортировано.

По пункту 3. Вы сказали в комментариях, что это хорошо, так что вот алгоритм, который я имею в виду.Это многословно с точки зрения имен переменных, но, надеюсь, это проясняет ситуацию.В общем, это не слишком сложно:

const result = subtractFromSet([4, 5, 6, 7, 8], 25);
console.log(result)

function subtractFromSet(numberSet, totalToSubtract) {
  return numberSet.map((currentMember, index, wholeSet) => {
    const remainingElements = wholeSet.length - index
    const averageToSubtract = totalToSubtract / remainingElements;
    
    const toSubtract = Math.min(averageToSubtract, currentMember);
    //modify both the total remaining to subtract and the current element
    totalToSubtract -= toSubtract;
    return currentMember - toSubtract;
  })
}

Чтобы объяснить это словами, вот что происходит

1. Вычитание значения из суммы набора аналогично вычитаниюзначение делится на размер набора от каждого члена.Таким образом, [4, 5, 6, 7, 8] - 25 будет 4 - 5, 5 - 5, 6 - 5 и т. Д.
2. Если мы не хотим отрицаний, то мы только вычитаем до текущего члена.Таким образом, с текущим членом 4 и средним значением 25 / 5 = 5 мы можем только вычесть 4.
3. . Чтобы распределить остаток, мы просто добавляем его обратно к общей сумме, чтобы вычесть оставшуюся часть.членов.Поэтому, когда мы доберемся до второго члена 5, среднее значение теперь равно (25 - 4) / (5 - 1), потому что мы не могли вычесть полное 5 среднее значение в первый раз, только 4, а оставшиеся элементы на один меньше.Это дает 5.25.

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

И последнее: как я уже сказал, входные данные должны быть отсортированы.Это можно легко сделать так:

const unsortedArray = [6, 4, 7, 8, 5];
const sortedArray = unsortedArray.sort((a, b) => a - b)

console.log(sortedArray);

Я упустил из вышеприведенного алгоритма, чтобы сосредоточиться на том, что мы на самом деле делаем с отсортированным вводом.

Общая сложность этого алгоритма довольно приличная- Приличная сортировка принесет вам O(n log(n)) сложность времени.Зависит от реализации сортировки и набора данных - 5 элементов, вероятно, будут отсортированы с помощью O(n^2) Bubblesort, но опять же, это 5 элементов, поэтому, вероятно, это не окажет никакого влияния.Запуск алгоритма вычитания прост O(n).Сложность пространства для вычитания составляет O(2n), потому что .map() делает копию массива.Я выбрал это, поскольку это немного чище, потому что у вас все еще есть вход.Но вы также можете выполнять вычитание на месте с минимальными изменениями, и это даст вам O(n) сложность пространства.

const input = [4, 5, 6, 7, 8];
subtractFromSet(input, 25);
console.log(input);

function subtractFromSet(numberSet, totalToSubtract) {
  numberSet.forEach((currentMember, index, wholeSet) => { //using .forEach instead of .map
    const remainingElements = wholeSet.length - index
    const averageToSubtract = totalToSubtract / remainingElements;
    
    const toSubtract = Math.min(averageToSubtract, currentMember);
    //modify both the total remaining to subtract and the current element
    totalToSubtract -= toSubtract;
    wholeSet[index] = currentMember - toSubtract; //modify the array directly
  })
}

Answer 5

Не ясно, что подразумевается под «эффективным» в данном вопросе.

Для алгоритма вы можете

• .map() вводить массив для ввода arr массив целых или десятичных знаков минус n число, деленное на ввод .length,map

• .filter() результаты массива map для элементов, значение которых превышает 0, not

• .filter() элементов массива map до элементов, больших или равных 0, .matches

• .reduce() not массива до суммы элементов, меньших 0, subtotal

• pass subtotal to Math.abs(), чтобы получить абсолютное значение целого числа, деленное на matches.length минус not.length, чтобы получить вычитаемое значение, которое будет применено кinput, N

• .map() map, где значение minuend меньше или равно 0 return 0, иначе возвращаемое значение минус N, с .toFixed(3) в цепочке, удовлетворяющей требованию 3 десятичных цифр, описанных как ожидаемый результат, приведен к числу с помощью оператора add +, результат

• return result

const nonNegativeSubtraction = (arr, n) => {
  const map = arr.map(x => x - (n / arr.length));
  const not = map.filter(x => x < 0);
  const matches = map.filter(x => x >= 0);
  const subtotal = not.reduce((a, b) => a + b);
  const N = Math.abs(subtotal) / (matches.length - not.length);
  const result = map.map(x => x <= 0 ? 0 : +(x - N).toFixed(3));
  return result;
}

const test = [0, 0, 1 - 0.333, 2 - 0.333, 3 - 0.333];

let input = [4,5,6,7,8]; // minuend

let n = 25; // subtrahend

let res = nonNegativeSubtraction(input, n); // result

console.log(res);

console.assert(JSON.stringify(test) !== JSON.stringify(res), [test, res]);