如何排序数组的数组，避免含同名元素的子数组相邻？

我被这个问题困扰了一周，希望能得到帮助或建议。我有一个表单，收集用户的firstName、lastName和song，将这些值存储为对象，所有song属性相同的对象会被存入同一个子数组，示例如下：

[
  [
    {
      firstName: "John",
      lastName: "Doe",
      song: "Rock",
    },
    {
      firstName: "Emily",
      lastName: "Jones",
      song: "Rock",
    },
    {
      firstName: "David",
      lastName: "Williams",
      song: "Rock",
    },
  ],
  [
    {
      firstName: "Alice",
      lastName: "Johnson",
      song: "Jazz",
    },
    {
      firstName: "John",
      lastName: "Doe",
      song: "Jazz",
    },
    {
      firstName: "Jane",
      lastName: "Smith",
      song: "Jazz",
    },
  ],
  [
    {
      firstName: "Jennifer",
      lastName: "Miller",
      song: "Pop",
    },
  ],
];

用户可添加多个人员并关联到特定歌曲（每个子数组的对象数量从1到30不等）。表单提交后得到的结果是一个包含多个子数组的父数组。

需求是对该父数组排序，确保所有子数组中，包含相同firstName和lastName的子数组不会相邻。例如上述示例中，"John Doe"同时存在于第一个和第二个子数组，这两个子数组不能相邻。

我尝试编写了compareArrays函数来检测两个子数组是否存在同名元素，若存在则将该子数组移到父数组末尾，但此方案无效，因为移到末尾的子数组未被再次比较，仍会出现相邻的情况。相关代码如下：

function compareArrays(array1, array2) {
      if (!array1 || !array2) {
        return false;
      }

      const length1 = array1.length;
      const length2 = array2.length;

      //iterate through each element of array1
      for (let i = 0; i < length1; i++) {
        //compare array[i] with each element of array2
        for (let j = 0; j < length2; j++) {
          if (
            array1[i].firstName === array2[j].firstName &&
            array1[i].lastName === array2[j].lastName
          ) {
            console.log("Match found!");
            return true; //A match was found
          }
        }
      }
      return false; //No match was found in array1
    }

随后我在pushMatchingToEnd函数中调用该方法：

function pushMatchingToEnd(parentArray) {
      let length = parentArray.length;
      let i = 0;

      while (i < length) {
        const currentArray = parentArray[i];
        let j = i + 1;

        while (j < length) {
          const nextArray = parentArray[j];

          // Compare the current array to the next array
          if (compareArrays(currentArray, nextArray)) {
            // If they match, push nextArray to the end of parentArray
            parentArray.push(nextArray);
            // Remove nextArray from its current position
            parentArray.splice(j, 1);
            // Decrement length to account for the added element
            length--;
            // Decrement j to stay at the same index in the next iteration
            j--;
          }

          j++;
        }

        // Move to the next array in parentArray
        i++;
      }
    }
pushMatchingToEnd(arrayOfArrays)

遗憾的是，这个解决方案无效，因为移到末尾的子数组未被比较，最终仍会有多个含同名元素的子数组相邻。请问是否有可行的解决方法？

之前的方法只做了单向扫描，把冲突元素移到末尾后没有重新验证整个序列，导致问题反复出现。以下是更可靠的解决思路：

1. 优化冲突检测效率 #

先给每个子数组生成用户唯一标识的集合（用firstName+lastName作为键），避免嵌套循环扫描，提升检测速度：

// 给子数组生成用户标识集合
function addUserSet(subArray) {
  const userSet = new Set();
  subArray.forEach(user => {
    userSet.add(`${user.firstName}-${user.lastName}`);
  });
  return { original: subArray, users: userSet };
}

// 检测两个子数组是否有重复用户
function hasConflict(groupA, groupB) {
  // 遍历较小的集合，提升效率
  const [smallSet, largeSet] = groupA.users.size <= groupB.users.size 
    ? [groupA.users, groupB.users] 
    : [groupB.users, groupA.users];
  
  for (const userId of smallSet) {
    if (largeSet.has(userId)) return true;
  }
  return false;
}

2. 贪心算法构建合法序列 #

构建新的结果数组，每次从剩余子数组中挑选第一个和结果最后一个元素无冲突的子数组加入。如果所有剩余子数组都冲突，就直接加入第一个（这是无法完全避免冲突时的妥协，多数场景下可找到合法序列）：

function rearrangeGroups(parentArray) {
  const processedGroups = parentArray.map(addUserSet);
  const result = [];

  if (processedGroups.length === 0) return [];
  result.push(processedGroups.shift());

  while (processedGroups.length > 0) {
    let targetIndex = -1;
    // 找第一个和结果最后一个元素无冲突的子数组
    for (let i = 0; i < processedGroups.length; i++) {
      if (!hasConflict(result[result.length - 1], processedGroups[i])) {
        targetIndex = i;
        break;
      }
    }

    if (targetIndex !== -1) {
      result.push(processedGroups.splice(targetIndex, 1)[0]);
    } else {
      // 无符合条件的，直接加入第一个剩余子数组
      result.push(processedGroups.shift());
    }
  }

  // 还原为原数组格式返回
  return result.map(group => group.original);
}

// 使用示例
const sortedArray = rearrangeGroups(arrayOfArrays);

3. 收尾修复（可选） #

如果要求绝对无相邻冲突，可在贪心排序后做一次扫描，修复可能存在的少量冲突：

function fixRemainingConflicts(arr) {
  const processed = arr.map(addUserSet);
  for (let i = 0; i < processed.length - 1; i++) {
    if (hasConflict(processed[i], processed[i+1])) {
      // 从i+2开始找第一个和i无冲突的元素交换
      for (let j = i + 2; j < processed.length; j++) {
        if (!hasConflict(processed[i], processed[j])) {
          [processed[i+1], processed[j]] = [processed[j], processed[i+1]];
          break;
        }
      }
    }
  }
  return processed.map(g => g.original);
}

// 先排序再修复
let finalArray = rearrangeGroups(arrayOfArrays);
finalArray = fixRemainingConflicts(finalArray);

方案优势 #

• 预处理用户集合将冲突检测复杂度从O(n*m)降至O(min(n,m))，处理大数组时效率更高。
• 贪心构建序列的方式确保每一步都优先选择合法子数组，避免了原方案中冲突元素移到末尾后无人验证的问题。
• 可选的修复步骤能处理贪心算法遗漏的少量冲突，确保最终序列符合要求。

内容的提问来源于stack exchange，提问作者Steven Wimer