Warm tip: This article is reproduced from serverfault.com, please click

How to reorder an Array to avoid consecutive duplicates

发布于 2020-11-28 19:39:25

I have an array of numbers [1,2,2,2,3,4,5]

What I want to do is to sort the array to avoid equal numbers consecutively [1,2,3,2,4,2,5]. but I don't want to delete any number from the array, in the worse case when the duplicated numbers are more than the other numbers I would like to put those that are impossible to merge in other arrays.

const original = [1,2,2,2,2,2,2,3,4];
const merged = [];
const rest = [];

For example [1,2,2,2,2,2,2,3,4] the result expected should be [2,1,2,3,2,4,2] and another array with [2,2] in the original array I have 6 times 2 and I was able to merge 4 of the six in the rest

    const original = [1,2,2,2,2,2,2,3,4];
    const merged = [2,1,2,3,2,4,2];
    const rest = [2,2];

I was trying to play with this algorithm but there is no way to get the respected result, this algorithm deletes the duplicates

const testArr = [1, 1, 2, 2, 3, 3, 1, 1, 1];
const compress = (arr, len = 0, canDelete = false) => {
   if(len < arr.length){
      if(canDelete){
         arr.splice(len, 1);
         len--;
      }
      return compress(arr, len+1, arr[len] === arr[len+1])
   };
   return;
};
compress(testArr);
console.log(testArr);

Any Idea on what is the best way to face this kind of problem?

Questioner
Yoandry Collazo
Viewed
0
Nir Gofman 2020-11-29 04:45:16

It was a very interesting one, here is my solution:


const original = [1,2,2,2,2,3,3,2,2,2,3,4]
console.log("Before: ", original)

let object_keys = {}

//Step 1: map all the values and how many times it duplicated
for(let val of original){
  if(object_keys[val]){
    object_keys[val]++
  }else{
    object_keys[val] = 1
  }
}

console.log(object_keys) // { '1': 1, '2': 7, '3': 3, '4': 1 }

//Step 2: Run over the object and create a new array. the method is each iterate, append new key

const get_the_most_duplicated_val = (object_keys, except) => {
  let max = 0
  let key = ''
  for(let v in object_keys){
    if(object_keys[v] > max && !except.includes(v)){
      max = object_keys[v]
      key = v
    }
  }
  return key
}

let merged = []
let rest = []

let merged_is_completed = false
while(!merged_is_completed){

  const append_val = (key) => {
    merged.push(key)
    object_keys[key]--
    if(object_keys[key] == 0){
      delete object_keys[key]
    }
  }

  const last_val = () => {
    return merged[merged.length - 1]
  }

  let most_key = get_the_most_duplicated_val(object_keys, [])
  append_val(most_key)
  let most_key2 = get_the_most_duplicated_val(object_keys, [most_key])
  append_val(most_key2)

  if(Object.keys(object_keys).length == 1){
    if(last_val() != Object.keys(object_keys)[0]){
      append_val(Object.keys(object_keys)[0])
    }
    for(let i=0;i<object_keys[Object.keys(object_keys)[0]];i++){
      rest.push(Object.keys(object_keys)[0])
    }
    merged_is_completed = true
  }
}
console.log("Merged: ", merged)
console.log("Rest: ", rest)

I put it in Codepen so you can test it by yourself :) https://codepen.io/gofmannir/pen/vYXEmPa?editors=0011