✏️ Partition Array According to Given Pivot на Go

LeetCode 2161. Задача простая, но даёт отличный повод вспомнить, как устроен один шаг быстрой сортировки.

Условие: есть массив nums и число pivot. Нужно переставить элементы так, чтобы сначала шли все числа меньше опорного, затем равные ему, потом большие.

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

➡️ Способ 1: три прохода

Самый прямой подход — пройти массив трижды:

• первый проход собирает всё, что меньше pivot;
• второй добавляет равные;
• третий — большие.

Порядок внутри каждой группы сохраняется сам собой: мы всегда идём слева направо:

func pivotArray(nums []int, pivot int) []int {
    res := make([]int, 0, len(nums))
    for _, v := range nums {
        if v < pivot {
            res = append(res, v)
        }
    }
    for _, v := range nums {
        if v == pivot {
            res = append(res, v)
        }
    }
    for _, v := range nums {
        if v > pivot {
            res = append(res, v)
        }
    }
    return res
}

Время — O(n), память — O(n). Три прохода по массиву длины n всё равно дают линейную сложность.

➡️ Способ 2: два указателя за один проход

А можно собрать ответ за один проход. Меньшие пишем слева, большие — справа, а середину потом заполняем опорным значением:

func pivotArray(nums []int, pivot int) []int {
    n := len(nums)
    res := make([]int, n)
    left, right := 0, n-1
    for i, j := 0, n-1; i < n; i, j = i+1, j-1 {
        if nums[i] < pivot {
            res[left] = nums[i]
            left++
        }
        if nums[j] > pivot {
            res[right] = nums[j]
            right--
        }
    }
    for left <= right {
        res[left] = pivot
        left++
    }
    return res
}

Как это работает:

• i бежит вперёд и кладёт меньшие числа в левую часть — в исходном порядке;

• j бежит назад и кладёт большие числа в правую часть.

Почему порядок больших не ломается? j движется с конца, поэтому более поздние большие элементы попадают правее — относительный порядок сохраняется.

После цикла промежуток между left и right остаётся под равные pivot. Его и дозаполняем.

❓ Что выбрать

Оба решения линейны по времени, разница в акцентах:

• три прохода читаются проще и отлично смотрятся на собеседовании, когда важна ясность;

• два указателя экономят проходы и делают всё за один цикл — это заметно на больших массивах.

Логика под капотом одна: бьём массив на три части и сохраняем исходный порядок меньших и больших.

📍 Навигация: Вакансии • Задачи • Собесы

🐸 Библиотека Go-разработчика

#ReadySetGo