The idea it to basically not have repeated values in the array with similar values.
An example input array:
input = [1,2,2,2,2,3,4,5,6,7,8,9] Expected output to be something like this:
desiredOutput = [1,2,3,2,4,2,5,2,6,2,7,8,9] I have tried putting this in a for loop where it checks with the next item and if it is same, swaps the values. The problem is when I have continuous similar values.
This proposal features
[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] = 4Make 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
kto the key of the biggest value of a property.k = '2'- If truthy, proceed. Otherwise go to 11.
Set
lto the value oflength[k].l = 4- Iterate over
land pushkto the end of the array with the index ofi % outputLength. Increasei.- Delete property
k.- Proceed with 5.
Return the flat
outputarray.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; }maybe that could help you:
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; } } The idea is to greedily put the highest frequency numbers first.
Construct a max heap where every node is a tuple that stores the number & it's frequency.
Then extract the head of the max heap (the highest frequency node) and add it's value to the resultant array.
If there's a previous element then add it back to the heap.
Decrement the frequency of the extracted node and store it in prev, so that it can be added back after one iteration.
Finally return the solution if it exists otherwise return the string "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])));Note: I've not implemented a Max Heap (because it's tedious), I've simulated it with Array.prototype.sort.
[9,2,3,1,4,2,5,2,6,2,7,8,2]