使用 JavaScript 混淆数组中的数字，使得没有两个相邻数字相同

Question

想法是在具有相似值的数组中基本上没有重复值。

输入数组示例：

input = [1,2,2,2,2,3,4,5,6,7,8,9]

预期输出如下所示：

desiredOutput = [1,2,3,2,4,2,5,2,6,2,7,8,9]

我试过将其放入 for 循环中，在其中检查下一项，如果相同，则交换值。问题是当我有连续的相似值时。

Answer 1

也许对您有帮助：

for(var i = 1; i < input.length; i++) {
    if(input[i-1] == input[i]) {
        var j = i;
        while(j < input.length && input[j] == input[i]) {
            j++;
        }
        var el = input[j];
        input[j] = input[i];
        input[i] = el;  
    }
}

Answer 2

此提案的特点

元素计数并将其存储在适当的对象中，
检查传播是否可能（例如此处不存在[1, 1, 1, 1, 3, 3]），
元素循环，所以
相同元素之间的最大距离。

How does it work?

As example I take this array: [1, 2, 2, 2, 2, 3, 4, 5, 6, 7, 8, 9]
Build an object with the count of the elements, store it with the element as key.
length = {
      "1": 1, "2": 4, "3": 1, "4": 1, "5": 1, "6": 1, "7": 1, "8": 1, "9": 1
  }
Select the property with the largest value: length[2] = 4
Make a new array with the length of the previous value and fill it with empty arrays.
output = [[], [], [], [], []]
Check if a spreaded array is possible. If not, return.
Set k to the key of the biggest value of a property.
k = '2'
If truthy, proceed. Otherwise go to 11.
Set l to the value of length[k].
l = 4
Iterate over l and push k to the end of the array with the index of i % outputLength. Increase i.

Delete property k.

Proceed with 5.
Return the flat output array.
output   first  then continued
array 0:     2     1     6
array 1:     2     3     7
array 2:     2     4     8
array 3:     2     5     9

return:      2  1  6  2  3  7  2  4  8  2  5  9
distance     |        |        |        |       is equal  

function spread(input) {

    function findMaxKey() {
        var max = 0, key;
        Object.keys(length).forEach(function (k) {
            if (length[k] > max) {
                max = length[k];
                key = k;
            }
        });
        return key;
    }

    var length = input.reduce(function (r, a) {
            r[a] = (r[a] || 0) + 1;
            return r;
        }, {}),
        i = 0, k = findMaxKey(), l,
        outputLength = length[k],
        output = Array.apply(Array, { length: outputLength }).map(function () { return []; });

    if (input.length - outputLength < outputLength - 1 ) {
        return; // no spread possible
    }
    while (k = findMaxKey()) {
        l = length[k];
        while (l--) {
            output[i % outputLength].push(k);
            i++;
        }
        delete length[k];
    }
    return output.reduce(function (r, a) { return r.concat(a) }, []);
}
console.log(spread([1, 2, 2, 2, 2, 3, 4, 5, 6, 7, 8, 9]));
console.log(spread([1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2]));
console.log(spread([1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3]));
console.log(spread([1, 1, 1, 1, 3, 3]));
console.log(spread([1, 1, 3]));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 3

使用最大堆的贪心方法

这个想法是贪婪地将频率最高的数字放在第一位。

构造一个最大堆，其中每个节点都是一个存储数字及其频率的元组。
然后提取最大堆的头部（频率最高的节点）并将其值添加到结果数组中。
如果有前一个元素，则将其添加回堆中。
将提取出的节点的频次递减存入prev，这样迭代一次后可以加回来
最后 return 解决方案，否则 return 字符串 "Not Possible".

function solution(arr) {
  const maxHeap = Array.from(
    arr.reduce((m, i) => m.set(i, (m.get(i) ?? 0) + 1), new Map())
  ).sort(([, a], [, b]) => b - a);
  
  const res = [];
  let prev = null;
  
  while (maxHeap.length) {
    const maxNode = maxHeap.shift();
    res.push(maxNode[0]);
    maxNode[1] -= 1;
    if (prev) {
      maxHeap.push(prev);
      maxHeap.sort(([, a], [, b]) => b - a);
      prev = null;
    }
    if (maxNode[1] > 0) {
      prev = maxNode;
    }
  }
  return res.length < arr.length ? "Not Possible" : res;
}

console.log(JSON.stringify(solution([1, 2, 2, 2, 2, 3, 4, 5, 6, 7, 8, 9])));
console.log(JSON.stringify(solution([1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2])));
console.log(JSON.stringify(solution([1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3])));
console.log(JSON.stringify(solution([1, 1, 1, 1, 3, 3])));
console.log(JSON.stringify(solution([1, 1, 3])));

注意：我没有实现最大堆（因为它很乏味），我用Array.prototype.sort.

模拟了它

使用 JavaScript 混淆数组中的数字，使得没有两个相邻数字相同

Jumble numbers in an array such that no two adjacent numbers are same using JavaScript

javascript

arrays

sorting

grouping

使用最大堆的贪心方法