Различные подходы к решению Leetcode 75 в JavaScript

Алгоритмы сортировки играют решающую роль в программировании. Хотя существует несколько известных алгоритмов сортировки, сортировка массива, содержащего только три отдельных элемента, представляет собой интересную задачу. Задача о голландском национальном флаге, названная в честь трехцветного голландского флага, представляет собой интригующий сценарий, в котором массив, состоящий из нулей, единиц и двоек, необходимо отсортировать за линейное время без использования дополнительного пространства.

В этой статье мы углубимся в проблему голландского национального флага и изучим эффективное решение для сортировки такого массива. Мы обсудим предысторию проблемы, наметим подход, используемый для ее решения, и предоставим пошаговое объяснение алгоритма. Кроме того, мы проанализируем его временную и пространственную сложность, чтобы понять его эффективность.

Постановка проблемы:

Дан массив nums с n объектами, окрашенными в красный, белый или синий цвет, отсортируйте их на месте, чтобы объекты одного цвета были смежными, а цвета располагались в следующем порядке: красный, белый и синий. синий.

Мы будем использовать целые числа 0, 1 и 2 для представления красного, белого и синего цветов соответственно.

Вы должны решить эту проблему, не используя библиотечную функцию сортировки.

Подход 1: сортировка подсчетом

Итак, идея состоит в том, чтобы перебрать массив и подсчитать количество 0, 1 и 2. Затем перезапишите исходный массив количеством каждого числа в правильном порядке.

  1. Сначала мы перебираем входной массив и подсчитываем вхождения каждого числа (0, 1 и 2).
  2. После подсчета вхождений мы снова проходим по входному массиву. Для каждого элемента мы проверяем его значение и используем информацию о счете, чтобы определить его правильную позицию в отсортированном массиве.
  3. После того, как мы перебрали весь входной массив, мы успешно перезаписали исходный массив отсортированными элементами в правильном порядке.
// ES6 Arrow Function
const sortColors = nums => {
    // count of 0s, 1s and 2s
    let count = [0, 0, 0];

    // count the occurrence of each number
    for(let num of nums) count[num]++;

    let index = 0;
    for(let i = 0; i < count.length; i++) {
        while(count[i] > 0) {
            nums[index] = i;
            count[i]--;
            index++;
        }
    }
}

Временная сложность: O(N)

Мы повторяем массив дважды, один раз для подсчета появления каждого числа, а затем перезаписываем исходный массив отсортированными числами. Обе эти операции происходят за линейное время.

Космическая сложность: O(1)

Сложность пространства постоянна, потому что дополнительное пространство, используемое для подсчета вхождений каждого числа, фиксировано. Это не зависит от размера входного массива.

Подход 2: Алгоритм за один проход

  1. Мы используем два указателя, один в начале и один в конце массива.
  2. Инициализируйте еще два указателя, чтобы отслеживать текущий обрабатываемый индекс и индекс, в который следует поместить следующий 0.
  3. Переберите массив, и если вы встретите 0, поменяйте его местами со следующим указателем позиции 0 и увеличьте оба указателя.
  4. Если вы встретите 2, поменяйте местами его с конечным указателем и уменьшите конечный указатель.
  5. Продолжайте перемещать текущий указатель, пока он не достигнет конечного указателя.
// ES6 Arrow Function
const sortColors = nums => {
    let low = 0, mid = 0, high = nums.length - 1;

    while(mid <= high) {
        if(nums[mid] === 0) {
            swap(nums, low, mid);
            low++;
            mid++;
        } else if(nums[mid] === 2) {
            swap(nums, mid, high);
            high--;
        } else {
            mid++;
        }
    }
}

// Swap Function
const swap = (arr, a, b) => [arr[a], arr[b]] = [arr[b], arr[a]];

Временная сложность: O(N)

Мы обходим массив только один раз с помощью двух указателей и выполняем операции с постоянным временем (перестановка элементов местами). Следовательно, временная сложность линейна.

Космическая сложность: O(1)

Поскольку мы изменяем входной массив на месте и не используем никаких дополнительных структур данных. Сложность пространства постоянна.

Подход 3: два указателя

  1. Инициализируйте указатель на 0, скажем, i. Этот указатель представляет собой границу между секцией отсортированных нулей и секцией отсортированных единиц.
  2. Теперь выполните итерацию по массиву, используя другой указатель, назовем его j. Этот указатель представляет текущий обрабатываемый элемент.
  3. Если элемент входного массива arr[j] равен 0, его необходимо поместить в секцию отсортированных нулей. Для этого поменяйте местами элемент с номером arr[i] на элемент с номером arr[j]. Затем увеличьте i, чтобы расширить раздел отсортированных нулей.
  4. После окончания первого цикла i будет указывать на индекс, с которого должна начинаться секция отсортированных единиц. Инициализируйте другой указатель с k на i для второго цикла.
  5. Повторите итерацию по массиву снова.
  6. Если элемент в arr[m] равен 1, его нужно поместить в раздел отсортированных 1. Для этого поменяйте местами элемент с номером arr[m] на элемент с номером arr[k]. Затем увеличьте k, чтобы расширить раздел отсортированных единиц.
  7. После завершения обоих циклов массив будет отсортирован в нужном порядке: все 0 слева, затем все 1 и, наконец, все 2.
// ES6 Arrow Function
const sortColors = nums => {
    let i = 0; 
    for(let j = 0; j < nums.length; j++) {
        if(nums[j] === 0) {
            swap(nums, i, j);
            i++;
        }
    }

    let k = i;
    for(let j = 0; j < nums.length; j++) {
        if(nums[j] === 1) {
            swap(nums, j, k);
            k++;
        }
    }
}

// Swap Function
const swap = (arr, a, b) => [arr[a], arr[b]] = [arr[b], arr[a]];

Временная сложность: O(N)

Мы делаем два прохода через входной массив, каждый из которых занимает линейное время, где n — длина массива. Поэтому общая временная сложность является линейной.

Космическая сложность: O(1)

Сложность пространства постоянна, поскольку мы не используем какую-либо дополнительную структуру данных, масштабируемую с размером входных данных. Все операции выполняются на месте.

И вот оно, ребята! Мы исследовали различные подходы, оптимизировали наши решения и, надеюсь, повеселились. Я надеюсь, что эта статья предоставила вам ценную информацию и помогла лучше понять различные подходы к решению этой проблемы. Удачного кодирования!

Проблема - Литкод 75