В этом уроке ты
- Решишь задачу с собеседования в BigTech.
- Освоишь технику “быстрый и медленный указатель” и научишься применять её на практике.
Задача с собеседования
Это одна из самых популярных задач на собеседованиях! Представь, что ты на собеседовании, и подумай, как бы ты решал эту задачу.
Условие
Дан массив nums. Нужно переместить все нули (0) в конец массива, при этом порядок остальных элементов должен сохраниться.
Необходимо изменять исходный массив напрямую, без создания нового массива для хранения результата.
Пример
Ввод: nums = [2,1,0,0,4,0,9] Вывод: [2,1,4,9,0,0,0]
В чём сложность задачи
Одна из самых первых идей, которая приходит в голову, — создать новый массив, скопировав в него все ненулевые элементы, а затем добавить нужное количество нулей:
using System;
using System.Collections.Generic;
public class Solution
{
// Время: O(n), где n - размер nums
// Память: O(n), где n - размер nums
public static List<int> MoveZeros(int[] nums)
{
// Создаем новый массив из не нулевых элементов
List<int> result = new List<int>();
foreach (int num in nums)
{
if (num != 0)
{
result.Add(num);
}
}
// Дополняем массив нулями
while (result.Count != nums.Length)
{
result.Add(0);
}
return result;
}
}#include <vector>
using namespace std;
// Время: O(n), где n - размер nums
// Память: O(n), где n - размер nums
vector<int> moveZeros(const vector<int>& nums) {
// Создаем новый массив из не нулевых элементов
vector<int> result;
for (int num : nums) {
if (num != 0) {
result.push_back(num);
}
}
// Дополняем массив нулями
while (result.size() != nums.size()) {
result.push_back(0);
}
return result;
}package main
// Время: O(n), где n - размер nums
// Память: O(n), где n - размер nums
func moveZeros(nums []int) []int {
// Создаем новый массив из не нулевых элементов
result := []int{}
for _, num := range nums {
if num != 0 {
result = append(result, num)
}
}
// Дополняем массив нулями
for len(result) < len(nums) {
result = append(result, 0)
}
return result
}package main
// Время: O(n), где n - размер nums
// Память: O(n), где n - размер nums
func moveZeros(nums []int) []int {
// Создаем новый массив из не нулевых элементов
result := []int{}
for _, num := range nums {
if num != 0 {
result = append(result, num)
}
}
// Дополняем массив нулями
for len(result) < len(nums) {
result = append(result, 0)
}
return result
}import java.util.ArrayList;
import java.util.List;
// Время: O(n), где n - размер nums
// Память: O(n), где n - размер nums
public class Solution {
public static List<Integer> moveZeros(List<Integer> nums) {
// Создаем новый массив из не нулевых элементов
List<Integer> result = new ArrayList<>();
for (int num : nums) {
if (num != 0) {
result.add(num);
}
}
// Дополняем массив нулями
while (result.size() < nums.size()) {
result.add(0);
}
return result;
}
}from typing import *
# Время: O(n), где n - размер nums
# Память: O(n), где n - размер nums
def move_zeros(nums: List[int]) -> List[int]:
# Создаем новый массив из не нулевых элементов
result = []
for num in nums:
if num != 0:
result.append(num)
# Дополняем массив нулями
while len(result) != len(nums):
result.append(0)
return resultРешение понятное, но не оптимальное с точки зрения памяти! Нужно изменить сам исходный массив, не создавая новый (то есть без дополнительной памяти). Именно решение без выделения дополнительной памяти и ждет интервьюер.
Оптимальное решение
Оптимальное решение достигается с помощью двух указателей:
p2(быстрый указатель) — двигается на каждой итерации и ищет очередной ненулевой элемент.p1(медленный указатель) — двигается только тогда, когдаp2указывает на ненулевой элемент. Его задача — указывать на позицию в массиве, куда нужно «положить» найденный ненулевой элемент.
using System;
using System.Collections.Generic;
public class Solution
{
public static List<int> MoveZeros(List<int> nums)
{
// Указывает на позицию, куда ставим следующий ненулевой элемент
int p1 = 0;
// Указывает на следующий ненулевой элемент
int p2 = 0;
while (p2 < nums.Count)
{
if (nums[p2] != 0)
{
(nums[p1], nums[p2]) = (nums[p2], nums[p1]);
p1++;
}
p2++;
}
return nums;
}
}#include <vector>
using namespace std;
vector<int> moveZeros(vector<int>& nums) {
// указывает на какую позицию поставим следующий элемент не равный 0
int p1 = 0;
// указывает на следующий не нулевой элемент
int p2 = 0;
while (p2 < nums.size()) {
if (nums[p2] != 0) {
swap(nums[p1], nums[p2]);
p1++;
}
p2++;
}
return nums;
}package main
// moveZeros перемещает нули в конец массива
func moveZeros(nums []int) []int {
// указывает на какую позицию поставим следующий элемент не равный 0
p1 := 0
// указывает на следующий не нулевой элемент
p2 := 0
for p2 < len(nums) {
if nums[p2] != 0 {
nums[p1], nums[p2] = nums[p2], nums[p1]
p1++
}
p2++
}
return nums
}import java.util.*;
public class Solution {
public static List<Integer> moveZeros(List<Integer> nums) {
// указывает на какую позицию поставим следующий элемент не равный 0
int p1 = 0;
// указывает на следующий не нулевой элемент
int p2 = 0;
while (p2 < nums.size()) {
if (nums.get(p2) != 0) {
Collections.swap(nums, p1, p2);
p1++;
}
p2++;
}
return nums;
}
}from typing import *
def move_zeros(nums: List[int]) -> List[int]:
# указывает на какую позицию поставим следующий элемент не равный 0
p1 = 0
# указывает на следующий не нулевой элемент
p2 = 0
while p2 < len(nums):
if nums[p2] != 0:
nums[p1], nums[p2] = nums[p2], nums[p1]
p1 += 1
p2 += 1
return numsexport function moveZeros(nums) {
// указывает на какую позицию поставим следующий элемент не равный 0
let p1 = 0;
// указывает на следующий не нулевой элемент
let p2 = 0;
while (p2 < nums.length) {
if (nums[p2] !== 0) {
[nums[p1], nums[p2]] = [nums[p2], nums[p1]];
p1++;
}
p2++;
}
return nums;
} Рассмотрим как будет работать решение при nums = [0,2,0,1]:
Паттерн “быстрый и медленный указатель”
Этот паттерн чаще всего применяется, когда необходимо перенести какие-то элементы (например, нули) в конец массива или провести замену, не используя дополнительный массив. При этом один указатель (медленный) обычно указывает на позицию для записи нужных элементов, а второй (быстрый) перебирает массив и выполняет основную логику поиска.
Кстати, паттерн “быстрый и медленный указатель” применяется к одному массиву!
Не всегда быстрый и медленный указатель двигаются от начала к концу — иногда применяется направление от конца к началу.
Скорее практиковаться!
Скорее переходи к задачкам и решай их, чтобы закрепить все полученные знания на практике!