сортировка массива (1,2,3) чисел за O (n) раз - PullRequest
Новая
       27

сортировка массива (1,2,3) чисел за O (n) раз

1 голос
/ 28 октября 2019

Учитывая список чисел только с 3 уникальными числами (1, 2, 3), отсортируйте список за O (n) время. Плюс сортируйте массив, используя постоянное пространство O (1) .

Пример:

Input: [3, 3, 2, 1, 3, 2, 1]

Output: [1, 1, 2, 2, 3, 3, 3]

Здесь решение, которое я принял (не является пробелом O (1) и имеет пустые пробелы в массиве ..): Что делает эта функция простой ... увеличивает размер расположения в два раза в случаечто все его элементы равны 2;Затем он переходит к своей предыдущей длине (current / 2) для сортировки своих элементов. Если он равен 1, он ничего не делает, если он находит 2, он помещает его в предыдущую максимальную длину +1, он увеличивает переменную len и удаляетэлемент и если это 3, нажмите и удалите элемент .. тогда у вас есть пустые места в массиве, и вы не встретите плюс проблемы, но это O (n). 

function sort(list) {
    let len = list.length;
    list.length=len*2
    for(let i=0; i<list.length/2; i++){
        let n=list[i]
        if(n==2){
            list[len]=n
            delete list[i]
            len++
        }else if(n==3){
            list.push(n)
            delete list[i]
        }
    }
    return list
}

console.log(sort([1,2,3,2,1,1]))

Ответы [ 4 ]

8 голосов
/ 28 октября 2019

Вы можете использовать алгоритм задачи с голландским национальным флагом :

Задача с голландским национальным флагом 1 - это проблема компьютерного программирования, предложенная Эдсгер Дейкстра (в главе своей книги Дисциплина программирования Прентис-Холл, 1976 г.). Флаг Нидерландов состоит из трех цветов: красного, белого и синего. Учитывая, что шары этих трех цветов расположены случайным образом в линию (фактическое количество шаров не имеет значения), задача состоит в том, чтобы расположить их так, чтобы все шары одного цвета были вместе, а их коллективные цветовые группы были в правильном порядке. 

var array = [3, 3, 2, 1, 3, 2, 1],
    MID = 2,
    i = 0,
    j = 0,
    n = array.length - 1;

while (j <= n) {
    if (array[j] < MID) {
        [array[i], array[j]] = [array[j], array[i]];
        i++;
        j++;
    } else if (array[j] > MID) {
        [array[n], array[j]] = [array[j], array[n]];
        n--;
    } else {
        j++;
    }
}

console.log(array);
2 голосов
/ 28 октября 2019

Вы можете сосчитать количество вхождений 1, 2, 3 и использовать эту информацию для воссоздания / получения отсортированного массива: 

const arr = [3, 3, 2, 1, 3, 2, 1]

const count = arr.reduce((acc, curr) => {
  acc[curr]++;
  return acc;
}, {1: 0, 2: 0, 3: 0})

arr.forEach((_, j) => {
  if (j < count[1])
    arr[j] = 1
  else if (j < count[1] + count[2])
    arr[j] = 2
  else
    arr[j] = 3
})

console.log(arr)
2 голосов
/ 28 октября 2019

Поскольку вы знаете, что массив может содержать только 3 элементов, вы можете выполнять итерацию по всему массиву для каждого из них (это означает, что алгоритм выполняется 3 * n раз =O(3n) = O(n)).

Ограничение пространства означает, что вам нужно работать на месте , значит, работать с входным массивом .

Это мое решение:] 

function swap(i, j, arr) {
  const currentVal = arr[j];
  arr[j] = arr[i];
  arr[i] = currentVal;
}

function sort(arr) {
  let globalIndex = 0;
  [1, 2, 3].forEach(item => {
    for (let i = globalIndex; i < a.length; i++) {
      if (arr[i] === item) {
        swap(i, globalIndex, arr);
        globalIndex++;
      }
    }
  });
}

const a = [1, 2, 3, 2, 1, 1];

sort(a);

console.log(a);
0 голосов
/ 28 октября 2019

По моему мнению, вы можете просто инициализировать три переменные как 0 для подсчета каждого 1 , 2 и 3 . Пройдите через массив один раз и увеличьте соответствующий счетчик на 1 для значений каждого индекса, т. Е. Если значение для определенного индекса равно 2, увеличьте вторую переменную на 1.

Как только вы получите счетчик, (Count1 - 1) th index будет последним вхождением 1, (Count1 + Count2 - 1) th index будет последним вхождением 2 и (Count1 + Count2 + Count3- 1) th index будет последним вхождением 3.

Вы можете пройти весь массив и назначить значения соответственно. Этот способ чем-то похож на Подсчет сортировки , но, конечно, не стабильный . Тем не менее, у вас есть другой вариант, как уже упоминалось в предыдущих ответах - Проблема голландского национального флага

...