如何对数组元素进行排序，使得相同元素的最大链长度最短（例如：AAAABC 到 ABACAA）？

Question

例如，我想减少相同元素的链的最大长度的长度，直到链的长度为最小，例如：

["A","A","B","B","A"] to ["A","B","A","B","A"] (max chain from 2:AA,BB to 1:A,B)
["A","A","A","B","B","C"] to ["A","B","A","B","A","C"] (max chain from 3:AAA to 1:A,B,C)
["A","A","A","A","B","C"] to ["A","A","B","A","C","A"] (max chain from 4:A to 2:A, not ["A","A","B","A","A","C"] because if max length of chains are the same, select one that contains less number of max length of chains)
["A","A","A","A","B","B"] to ["A","B","A","A","B","A"] (also not ["A","A","B","A","A","B"] because it has 2 AA instead of 1)

如何编写函数来排序？我试过：

["A","A","B","B","A"] to ["A","B","A","B","A"] (max chain from 2:AA,BB to 1:A,B)
["A","A","A","B","B","C"] to ["A","B","A","B","A","C"] (max chain from 3:AAA to 1:A,B,C)
["A","A","A","A","B","C"] to ["A","A","B","A","C","A"] (max chain from 4:A to 2:A, not ["A","A","B","A","A","C"] because if max length of chains are the same, select one that contains less number of max length of chains)
["A","A","A","A","B","B"] to ["A","B","A","A","B","A"] (also not ["A","A","B","A","A","B"] because it has 2 AA instead of 1)

它计算每个元素均匀分布在数组原始长度中的位置，然后对均匀分布的位置进行排序，但输出是["A","A","A","A","B","C"]而["A","B","C","A","A","A"]不是["A","A","B","A","C","A"]。

这里不需要维护其他元素的顺序，并且最短链规则应该适用于“A”和“B”（所有其他元素），而不是仅适用于“C”，其他示例：

AABBBCCCCCCCC to CBCBCACACCBCC (two 2C chains)
AABBBCCCCCCCCCCCCCC to CCCBCCBCCACCACCBCCC (two 3C chains)
AAABBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCC to CCACCACCACCBCCCBCCCBCCCBCCCBCCCBCCC (six 3C chains)

Answer 1

获取您的countMap条目，以便获得每个字符及其频率 - 这样，您可以迭代条目，在剩下的两个最大的条目之间交替，直到完全耗尽。（例如，给定 10 个 X、10 个 Y 和 1 个 Z，通过认识到 X 和 Y 仍然是两个最高计数，直到它们减少到剩下 1，您可以将 Z 保留到接近结束为止）

const magicSort = (arr) => {
  const countMap = {};
  for (const e of arr){
    countMap[e] = (countMap[e] || 0) + 1;
  }
  const entries = Object.entries(countMap);
  const sorted = [];
  let last;
  while (entries.length) {
    const entry = entries.reduce((a, b) => {
      // Return new value if current value is a dupe
      if (a[0] === last) return b;
      // Return current value if new value is a dupe
      if (b[0] === last) return a;
      // Return entry with highest count
      return b[1] > a[1] ? b : a;
    });
    last = entry[0];
    sorted.push(last);
    entry[1]--;
    if (!entry[1]) {
      entries.splice(entries.indexOf(entry), 1);
    }
  }
  console.log(sorted);
};
magicSort(["A","A","B","B","A"]);
magicSort(["A","A","B","B","C"]);
magicSort(["A","A","A","A","B","C"]);
magicSort(["A","A","B","B","B","C","C","C","C","C","C"]);