如何排序数组使相同元素的最长连续链最短？

我们需要对数组元素排序，达成两个核心目标：

1. 让相同元素的最长连续链长度尽可能短；
2. 当最长链长度相同时，选择最长链数量更少的结果。

需求示例 #

["A","A","B","B","A"] 调整为 ["A","B","A","B","A"]（最长链从2变为1）
["A","A","A","B","B","C"] 调整为 ["A","B","A","B","A","C"]（最长链从3变为1）
["A","A","A","A","B","C"] 调整为 ["A","A","B","A","C","A"]（最长链从4变为2，优于["A","A","B","A","A","C"]，因为前者最长链数量仅1个）
["A","A","A","A","B","B"] 调整为 ["A","B","A","A","B","A"]（优于["A","A","B","A","A","B"]，前者最长链数量为1，后者为2）

尝试的代码及问题 #

我尝试了以下JavaScript实现，但存在逻辑缺陷：

const magicSort=function(arr){
  const countMap={};
  for(const e of arr){
    countMap[e]==null?countMap[e]=1:countMap[e]++;
  }
  const positionArr=[];
  for(const key of Object.keys(countMap)){
    for(let i=0;i<countMap[key];i++){
      positionArr.push({"key":key,"value":i/countMap[key]});
    }
  }
  positionArr.sort(function(a,b){
    return a.value-b.value;
  });
  for(let i=0;i<positionArr.length;i++){
    positionArr[i]=positionArr[i].key;
  }
  document.write(JSON.stringify(positionArr));
  document.write("<br/>");
}
magicSort(["A","A","B","B","A"]);
magicSort(["A","A","B","B","C"]);
magicSort(["A","A","A","A","B","C"]);

这段代码试图通过计算元素的均匀分布位置排序，但处理["A","A","A","A","B","C"]时输出为["A","B","C","A","A","A"]，不符合预期的["A","A","B","A","C","A"]。

补充示例 #

AABBBCCCCCCCC 调整为 CBCBCACACCBCC（两条长度为2的C连续链）
AABBBCCCCCCCCCCCCCC 调整为 CCCBCCBCCACCACCBCCC（两条长度为3的C连续链）
AAABBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCC 调整为 CCACCACCACCBCCCBCCCBCCCBCCCBCCCBCCC（六条长度为3的C连续链）

实现思路 #

核心是优先处理出现次数最多的元素，尽可能将其分散插入结果，同时控制最长链的长度与数量：

1. 统计每个元素的出现次数，按次数降序排序（次数相同则按元素标识排序）；
2. 构建结果时，优先选择与结果末尾元素不同的、剩余次数最多的元素，避免连续链过长；当无其他元素可选时，才继续添加当前元素（此时形成连续链，但尽可能控制长度）；
3. 当最长链长度确定后，优先让连续链集中，减少最长链的数量。

最终实现代码 #

function magicSort(arr) {
    // 统计元素出现次数
    const countMap = {};
    for (const e of arr) {
        countMap[e] = (countMap[e] || 0) + 1;
    }

    // 转换为[{key, count}]数组，按count降序排序
    let elements = Object.entries(countMap).map(([key, count]) => ({ key, count }));
    elements.sort((a, b) => b.count - a.count || a.key.localeCompare(b.key));

    const result = [];
    let lastKey = null;

    while (elements.length > 0) {
        // 找到可插入的元素：优先选与lastKey不同的最高频元素
        let selectedIndex = 0;
        if (elements[0].key === lastKey) {
            selectedIndex = elements.findIndex(el => el.key !== lastKey && el.count > 0);
            // 无其他元素可选时，只能继续取当前元素
            if (selectedIndex === -1) {
                selectedIndex = 0;
            }
        }

        const selected = elements[selectedIndex];
        result.push(selected.key);
        lastKey = selected.key;

        // 更新剩余次数，移除次数为0的元素
        selected.count--;
        if (selected.count === 0) {
            elements.splice(selectedIndex, 1);
        } else {
            // 重新排序，保证剩余高频元素在前列
            elements.sort((a, b) => b.count - a.count || a.key.localeCompare(b.key));
        }
    }

    return result;
}

// 测试用例
console.log(magicSort(["A","A","B","B","A"])); // ["A","B","A","B","A"]
console.log(magicSort(["A","A","A","B","B","C"])); // ["A","B","A","B","A","C"]
console.log(magicSort(["A","A","A","A","B","C"])); // 输出符合要求的分散结果，最长链为2且数量1
console.log(magicSort(["A","A","A","A","B","B"])); // ["A","B","A","B","A","A"]

代码说明 #

1. 统计与排序：先统计元素出现次数，按次数降序排列，确保优先处理高频元素；
2. 元素选择逻辑：每次优先选择与结果末尾不同的高频元素，避免连续链过长；无其他元素可选时才继续添加当前元素，控制连续链长度；
3. 动态重排序：每次取完元素后重新排序剩余元素，保证高频元素始终优先被处理，维持分散策略的有效性。

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