Хакаем массивы

В этом уроке ты

Решишь задачу с собеседования в BigTech.
Увидишь наглядно пример, когда маленькие хитрости (не всегда очевидные) упрощают решение, доводя его до оптимального.

Задача с собеседования

Представь, что ты пришёл на собеседование. Интервьюер уже ждёт тебя и озвучивает условие задачи…

Условие

Дан массив целых чисел nums, содержащий n целых чисел в диапазоне [0,n] включительно. Нужно вернуть единственное число из диапазона [0,n], которое отсутствует.

В массиве nums гарантированно отсутствует только одно число, остальные встречаются ровно один раз.

Пример 1

Ввод: nums = [3,1,5,0,2]
Вывод: 4
Объяснение: в массиве есть все числа от 0 до 5, кроме 4.

Пример 2

Ввод: nums = [1,2]
Вывод: 0

В чем сложность задачи?

Можно попытаться решить данную задачу через сортировку. Далее последовательно пройти по отсортированному массиву с поиском “пробела”, пропущенного числа.

using System;
using System.Collections.Generic;

public class Solution
{
    public static int MissingNumber(List<int> nums)
    {
        int n = nums.Count;

        // Сортируем массив
        nums.Sort();

        // Проходим по каждому индексу массива
        for (int i = 0; i < n; i++)
        {
            // Если число не совпадает с индексом,
            // значит мы нашли отсутствующее число
            if (nums[i] != i)
            {
                return i;
            }
        }

        // Если все числа соответствуют индексам,
        // отсутствует последнее число n
        return n;
    }
}

#include <vector>
#include <algorithm>

using namespace std;

int missingNumber(vector<int>& nums) {
    int n = nums.size();
    
    // Сортируем массив
    sort(nums.begin(), nums.end());
    
    // Проходим по каждому индексу массива
    for (int i = 0; i < n; i++) {
        // Если число не совпадает с индексом,
        // значит мы нашли отсутствующее число
        if (nums[i] != i) {
            return i;
        }
    }

    // Если все числа соответствуют индексам,
    // отсутствует последнее число n
    return n;
}

package main

import "sort"

func missingNumber(nums []int) int {
    n := len(nums)

    // Сортируем массив
    sort.Ints(nums)

    // Проходим по каждому индексу массива
    for i := 0; i < n; i++ {
        // Если число не совпадает с индексом,
        // значит мы нашли отсутствующее число
        if nums[i] != i {
            return i
        }
    }

    // Если все числа соответствуют индексам,
    // отсутствует последнее число n
    return n
}

import java.util.Arrays;

public class Main {
    public static int missingNumber(int[] nums) {
        int n = nums.length;

        // Сортируем массив
        Arrays.sort(nums);

        // Проходим по каждому индексу массива
        for (int i = 0; i < n; i++) {
            // Если число не совпадает с индексом,
            // значит мы нашли отсутствующее число
            if (nums[i] != i) {
                return i;
            }
        }

        // Если все числа соответствуют индексам,
        // отсутствует последнее число n
        return n;
    }
}

def missing_number(nums):
    n = len(nums)
    
    # Сортируем массив
    nums.sort()
    
    # Проходим по каждому индексу массива
    for i in range(n):
        # Если число не совпадает с индексом,
        # значит мы нашли отсутствующее число
        if nums[i] != i:
            return i
    
    # Если все числа соответствуют индексам,
    # отсутствует последнее число n
    return n

function missingNumber(nums) {
    const n = nums.length;

    // Сортируем массив
    nums.sort((a, b) => a - b);

    // Проходим по каждому индексу массива
    for (let i = 0; i < n; i++) {
        // Если число не совпадает с индексом, 
        // значит мы нашли отсутствующее число
        if (nums[i] !== i) {
            return i;
        }
    }

    // Если все числа соответствуют индексам, 
    // отсутствует последнее число n
    return n;
}

Это решение не оптимально по времени, так как использует встроенную сортировку, которая обычно работает за O(n*log(n)). Интервьюер не одобрит такое решение, поскольку оно будет медленным с большими массивами. Тебя попросят найти более эффективный подход.

Как решить эффективно?

Стоит обратить внимание, что по условию числа идут подряд. Значит если мы возьмем сумму чисел от 0 до n и вычтем сумму элементов входного массива, то получим требуемое.

using System;
using System.Collections.Generic;

public class Solution
{
    public static int MissingNumber(List<int> nums)
    {
        int n = nums.Count;

        // Вычисляем сумму первых n чисел
        int total = 0;
        for (int i = 0; i <= n; ++i) // Время: O(n)
        {
            total += i;
        }

        // Вычисляем сумму элементов массива
        int sumNums = 0;
        foreach (int num in nums) // Время: O(n)
        {
            sumNums += num;
        }

        // Возвращаем разницу
        return total - sumNums;
    }
}

using System;
using System.Collections.Generic;

public class Solution
{
    public static int MissingNumber(List<int> nums)
    {
        int n = nums.Count;

        // Вычисляем сумму первых n чисел
        int total = 0;
        for (int i = 0; i <= n; ++i) // Время: O(n)
        {
            total += i;
        }

        // Вычисляем сумму элементов массива
        int sumNums = 0;
        foreach (int num in nums) // Время: O(n)
        {
            sumNums += num;
        }

        // Возвращаем разницу
        return total - sumNums;
    }
}

package main

func missingNumber(nums []int) int {
    n := len(nums)
    
    // Вычисляем сумму первых n чисел
    total := 0
    for i := 0; i <= n; i++ { // Время: O(n)
        total += i
    }

    // Вычисляем сумму элементов массива
    sumNums := 0
    for _, num := range nums { // Время: O(n)
        sumNums += num
    }

    // Возвращаем разницу
    return total - sumNums
}

import java.util.List;

public class Solution {
    
    public static int missingNumber(List<Integer> nums) {
        int n = nums.size();
        
        // Вычисляем сумму первых n чисел
        int total = 0;
        for (int i = 0; i <= n; i++) { // Время: O(n)
            total += i;
        }
        
        // Вычисляем сумму элементов массива
        int sumNums = 0;
        for (int num : nums) { // Время: O(n)
            sumNums += num;
        }
        
        // Возвращаем разницу
        return total - sumNums;
    }
}

def missing_number(nums):
    n = len(nums)
    # Вычисляем сумму первых n чисел
    total = 0
    for i in range(n + 1): # Время: O(n)
        total += i
    # Вычисляем сумму элементов массива
    sum_nums = sum(nums) # Время: O(n)
    # Возвращаем разницу
    return total - sum_nums

export function missingNumber(nums) {
    const n = nums.length;
    
    // Вычисляем сумму первых n чисел
    let total = 0;
    for (let i = 0; i <= n; i++) { // Время: O(n)
        total += i;
    }
    
    // Вычисляем сумму элементов массива
    let sumNums = 0; // Время: O(n)
    for (let num of nums) {
        sumNums += num;
    }
    
    // Возвращаем разницу
    return total - sumNums;
}

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

using System;
using System.Collections.Generic;

public class Solution
{
    public static int MissingNumber(List<int> nums)
    {
        int n = nums.Count;
        // сумма чисел от 0 до n
        int overallSum = n * (n + 1) / 2; 
        int actualSum = 0;

        foreach (int num in nums)
        {
            actualSum += num;
        }

        return overallSum - actualSum;
    }
}

#include <vector>
using namespace std;

int missingNumber(const vector<int>& nums) {
    int n = nums.size();
    // сумма чисел от 0 до n
    int overallSum = n * (n + 1) / 2; 
    int actualSum = 0;

    for (int num : nums) {
        actualSum += num;
    }
    return overallSum - actualSum;
}

package main

func missingNumber(nums []int) int {
    n := len(nums)
    // сумма чисел от 0 до n
    overallSum := n * (n + 1) / 2 
    actualSum := 0

    for _, num := range nums {
        actualSum += num
    }

    return overallSum - actualSum
}

import java.util.List;

public class Solution {
    public int missingNumber(List<Integer> nums) {
        int n = nums.size();
        // сумма чисел от 0 до n
        int overallSum = n * (n + 1) / 2; 
        int actualSum = 0;

        for (int num : nums) {
            actualSum += num;
        }

        return overallSum - actualSum;
    }
}

from typing import *

def missing_number(nums: List[int]) -> int:
    n: int = len(nums)
    # сумма чисел от 0 до n
    overall_sum = n * (n + 1) // 2 
    return overall_sum - sum(nums)

export function missingNumber(nums) {
    const n = nums.length;
    // сумма чисел от 0 до n
    const overallSum = (n * (n + 1)) / 2; 
    return overallSum - nums.reduce((a, b) => a + b, 0);
}

В результате простых действий нам удалось хакнуть массив! Мы нашли пропущенный элемент, не сортируя его, всего за один проход! А память использовали лишь для хранения пары итоговых сумм.

Оценка по времени и памяти

Время: O(n), где n - размер nums
Память: O(1)

Что дальше

На примере такой простой задачи ты увидел, что порой полезно найти трюк, существенно упрощающий решение. Обычно это формула, основанная на определенной закономерности в последовательности чисел, или формула, связанная с операциями, выполняемыми над элементами массива. Скорее переходи к решению задач, чтобы отточить полученное знание на практике!