JavaScriptで配列要素を再配置！隣接する重複をなくす並べ替えアルゴリズム

問題

リテラル値からなる配列 arr を第一引数（唯一の引数）として受け取るJavaScriptの関数を作成します。この配列には、隣接して並んでいる重複した値がいくつか含まれています。

関数の役割は、隣り合う2つの要素が同じ値にならないように配列の要素を並べ替えることです。ただし、そのような並べ替えが少なくとも1つは存在することが保証されているものとします。関数は再配置後の配列を返します。

たとえば、関数への入力が次の場合を考えてみましょう。

const arr = [7, 7, 7, 8, 8, 8];

このとき、期待される出力は次のとおりです。

const output = [7, 8, 7, 8, 7, 8];

出力の説明

上記以外にも、条件を満たす正しい並べ替えのパターンは複数存在します。重要なのは「同じ値が隣接しないこと」です。

アルゴリズムの考え方

この問題は、次の手順で解くことができます。

• reduce() を使って、各要素の出現回数をカウントします。
• 出現回数に基づいて要素（キー）をソートします。
• まず偶数番目のインデックス（0, 2, 4, …）に、出現回数の多い要素から順に埋めていきます。
• 続いて奇数番目のインデックス（1, 3, 5, …）に残りの要素を埋めます。

この方法により、最も出現回数の多い要素どうしが隣接するのを避けられます。有効な並べ替えが存在する限り（最大出現回数が (n + 1) / 2 を超えない限り）、この手法で必ず条件を満たす配列が得られます。

実装例

実際のコードは次のようになります。

const arr = [7, 7, 7, 8, 8, 8];
const rearrangeArray = (arr = []) => {
   const map = arr.reduce((acc, val) => {
      acc[val] = (acc[val] || 0) + 1;
      return acc;
   }, {});
   const keys = Object.keys(map).sort((a, b) => map[a] - map[b]);
   const res = [];
   let key = keys.pop();
   for(let i = 0; i < arr.length; i += 2){
      if(map[key] <= 0){
         key = keys.pop();
      };
      map[key] -= 1;
      res[i] = Number(key);
   };
   for(let i = 1; i < arr.length; i += 2){
      if(map[key] <= 0){
         key = keys.pop();
      };
      map[key] -= 1;
      res[i] = Number(key);
   };
   return res;
};
console.log(rearrangeArray(arr));

出力

コンソールには次のように出力されます。

[ 8, 7, 8, 7, 8, 7 ]

この結果では、7 と 8 が交互に配置されており、同じ値が隣接していません。目的どおりの並べ替えが実現できています。