Найти все точки На линии, где расстояние между каждой из них делиться на Х


недавно я получил ( в ходе собеседования) наша задача написать метод для нахождения наибольшего подмножества точек, где расстояние между ними разделить на заданное число.

пример массива A =[-3,-2,1,0,8,7,1]

пример номер мы будем разделять по 3

поэтому для массива выше самое большое подмножество [-2,1,7,1]
потому что:

расстояние между точками рассчитывается следующим образом АБС(а[1] - в[2]) = 3

расстояние между точками 7 и -2-9 --> 9 % 3 = 0 так хорошо.

Я написал код:

var A = [-3, -2, 1, 0, 8, 7, 1];
    var biggestArray = [];
    (A).forEach(element => {
        Z=[];
        Z.push(element);
        for (i = 0; i < A.length; i++) {
            if (element !== A[i]) {
                var distance = Math.abs(element - A[i]);
                if (distance % 3 === 0) {
                    Z.push(A[i]);
                }
            }

        }
        if(Z.length>biggestArray.length){
            biggestArray=Z;
        }
    });
    console.log("biggest Array length:"+biggestArray.length);
    console.log("points: "+biggestArray);

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

Эта задача, кажется, довольно легко ( я не вижу что-то?) Также оно будет совершено N^2 операций. Есть ли хороший способ, чтобы тон его вниз?



105
0
задан 14 февраля 2018 в 04:02 Источник Поделиться
Комментарии
2 ответа

Я думаю, что на каждой итерации можно удалить элементы, которые вы включите в Zт. е. ваша первая итерация вернется [-3, 0] чтобы вы могли удалить их от AОни никогда не будет соответствовать все остальное. Мое решение будет:



let input      = [-3, -2, 1, 0, 8, 7, 1];
let result = [];
let workingSet = input;

while (workingSet.length) {
let first = workingSet[0];
let elements = [];
let unused = [];

workingSet.forEach( value => {
if ((value - first) % 3 == 0) {
elements.push(value);
} else {
unused.push(value);
}
});

console.log('elements', elements);
if (elements.length > result.length)
result = elements;
workingSet = unused;
}

console.log('result', result);



Одно замечание заключается в том, что вы смешиваете старый стиль JS-код, как var С ES6 в особенности, как =>. Я бы ожидать, что код либо использовать старый стиль JS для максимальной совместимости браузера или придерживаться нового стиля в JS последовательно.

1
ответ дан 14 февраля 2018 в 05:02 Источник Поделиться

Разница цифр будет кратна N, если и только если их мод значение N-это то же самое. Поэтому вы можете просто группировать числа на основе их мод значением N, и взять самый большой. Это требуется только один проход на входе, который является o(n) сложность, а не о(N2).



console.log(largestSubsetWithDistance([-3, -2, 1, 0, 8, 7, 1], 3));

function largestSubsetWithDistance(nums, diff) {
let result = [];
for(let i = 0; i < nums.length; i++) {
let mod = nums[i] % diff;
if(mod < 0) mod += diff; //Brings negative numbers into the 0 to N-1 range
if(!result[mod]) result[mod] = [];
result[mod].push(nums[i]);
}
return result.reduce((a,c) => c.length > a.length ? c : a, []);
}




1
ответ дан 15 февраля 2018 в 11:02 Источник Поделиться