@teertsneerg

Как наиболее быстро перебрать массив?

Имеется массив, например [1 , 3 , 10 , 11 , 18 , 5] , в данном массиве указаны координаты "плиток" на прямой.

Нужно составить "Дороги", разница в координатах между плитками должна быть не более X (для примера возьмём 2), все элементы используются только один раз. Все элементы из которых нельзя составить дорогу записывать в отдельный массив, идём строго по-порядку.

1) Проходим массив первый раз, с первого элемента и получаем дорогу 1,3,5 , эти элементы использовать больше нельзя, т.е. у нас остался массив [10 , 11 , 18]

2) Проходим оставшийся массив второй раз и получаем дорогу 10, 11, остался массив [18]

3) Проходим оставшийся массив третий раз и записываем 18 в отдельный массив.

Собственно сам вопрос: как лучше организовать подобный перебор массива (с наибольшей скоростью) , с удалением использованных элементов? Элементов, естественно, в разы больше, чем в примере.
  • Вопрос задан
  • 82 просмотра
Пригласить эксперта
Ответы на вопрос 4
Delgus
@Delgus
Я бы примерно так накатал за 15 минут
arr = [1 , 3 , 10 , 11 , 18 , 5];
x = 2;

arr.sort((a,b) => a > b);

result = [];
currentResultIndex = 0;
result.push([]);
result[currentResultIndex].push(arr[0]);

for(let i in arr) {
  if(i == 0) {
    continue;
  }
  if(arr[i] - arr[i-1] > x) {
    currentResultIndex++;
    result.push([]);
  }
  result[currentResultIndex].push(arr[i]);
}

console.log(result);

Можно код подулучшить и соптимизировать, я в js не огонь.
В result массив с дорогами.
Ответ написан
john36allTa
@john36allTa
That`s calling Walker
function* routes(coords, limit){
	coords = coords.sort( (a,b) => a - b );
	for (let i = 1; i < coords.length; i++)
		if (coords[i] - coords[i-1] > limit){
			yield coords.splice(0, i);
			i = 1;
		}
	if (coords.length > 0) yield coords;
}

let arr = [1 , 3 , 10 , 11 , 18 , 5], x = 2;

for (let route of routes(arr,x))
	console.log(`Path found: ${route.join(', ')}`)
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы