@MariaCorneva

Как отсортировать массив массивов строк в js?

Нужно выстроить вот такой массив:
[['butter', 'jelly'], ['bananas', 'apples'], ['peanuts', 'butter'], ['jelly', 'bananas']]


Вот в такой последовательности:
[['peanuts', 'butter'], ['butter', 'jelly'], ['jelly', 'bananas'], ['bananas', 'apples']]


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

Вот такой код срабатывает, но не всегда (не для всех кейсов):
routes.sort(([a, b], [c, d]) => {
     return b === c ? -1 : a === d ? 1 : 0 
})


Полагаю, нужно добавить еще условий. Вообще, алгоритм связан с направленными графами и на взрослых языках решается с помощью HashMap и reversed Hash Map, однако в JS вариант с сортировкой кажется самым лаконичным (эффективность не имеет значения)
  • Вопрос задан
  • 170 просмотров
Решения вопроса 1
bingo347
@bingo347 Куратор тега JavaScript
Ткнуть в доку лучше готового к копипасте ответа
Данная задача в принципе не решается сортировкой, так как сортировка это про отношение больше/меньше/равно, которого в данном случае нет.
Самое простое здесь, это построить из этих элементов двусвязный список, а затем преобразовать его в результирующий массив:
function orderArray(arr) {
  // для начала построим ноды списка и соберем их в 2 HashMap по обоим строкам
  const maps = arr.reduce((acc, item) => {
    const node = {item, next: null, prev: null};
    acc[0][item[0]] = node;
    acc[1][item[1]] = node;
    return acc;
  }, [{}, {}]);

  // после пройдемся по обоим HashMap и соединим связи
  for(const key of Object.keys(maps[0])) {
    maps[0][key].next = maps[0][maps[0][key].item[1]] || null;
  }
  for(const key of Object.keys(maps[1])) {
    maps[1][key].prev = maps[1][maps[1][key].item[0]] || null;
  }

  // найдем начальную ноду списка (ноду без предыдущей ноды)
  let cur = Object.values(maps[0]).find(({prev}) => prev === null);

  // и начиная с нее соберем список в массив
  const result = [];
  while(cur) {
    result.push(cur.item);
    cur = cur.next;
  }

  return result;
}

console.log(orderArray([['butter', 'jelly'], ['bananas', 'apples'], ['peanuts', 'butter'], ['jelly', 'bananas']]));
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
WblCHA
@WblCHA
Раз такое дело, Дмитрий Беляев, Роман, оцените.)
(() => {
  const orderArray = (arr) => {
    const itemsForMap = arr.map((items) => ([items[0], { items, prev: undefined }]))
    const itemsMap = new Map(itemsForMap);

    let last;
    itemsMap.forEach((node) => {
      const next = itemsMap.get(node.items[1]);
      if(next) {
        next.prev = node;
      }
      else {
        last = node;
      }
    });

    const result = [];
    result.length = arr.length;

    let current = last;
    for(let i = result.length - 1; i > -1; i--) {
      result[i] = current.items;
      current = current.prev;
    }

    return result;
  };
  
  return orderArray([['butter', 'jelly'], ['bananas', 'apples'], ['peanuts', 'butter'], ['jelly', 'bananas']]);
})()

Вроде всё верно, но я это в 7 утра перед сном писал...
Ответ написан
Ваш ответ на вопрос

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

Войти через центр авторизации
Похожие вопросы
от 75 000 до 180 000 ₽
Artezio Нижний Новгород
от 130 000 до 180 000 ₽
Intspirit Краснодар
от 80 000 до 150 000 ₽