1920.Build Array from Permutation

Ссылка на задачу: https://leetcode.com/problems/build-array-from-permutation/description/

Описание

Дана 0-indexed перестановка чисел nums. Необходимо сконструировать массив ans такой же длины, в котором каждый элемент ans[i] = nums[nums[i]] для каждого индекса i, удовлетворяющего условию 0 <= i < nums.length.

0-indexed перестановка чисел - это массив различных чисел от 0 до nums.length - 1 включительно.

Примечания

0-indexed означает то, что индексация элементов в массиве начинается с нуля.

Примеры

Пример 1

Input:

0	2	1	5	3	4

Output:

0	1	2	4	5	3

Пример 2

Input:

5	0	1	2	3	4

Output:

4	5	0	1	2	3

Ограничения

1 <= nums.length <= 1000
0 <= nums[i] <= nums.length
элементы nums не повторяются

Решение

Способ 1

Данный способ предполагает решение “в лоб”. Суть кроется в описании: необходимо просто сконструировать новый объект (массив), каждый элемент которого находить по формуле, приведенной выше (ans[i] = nums[nums[i]]).

Алгоритм:

Инициализируем массив известной длины nums.length
Итерируемся циклом от 0 до nums.length - 1 включительно
Элемент на текущей итерации находим по формуле ans[i] = nums[nums[i]]

Код:

python

class Solution:
    def buildArray(self, nums: List[int]) -> List[int]:
        ans = [-1] * len(nums)
        for i in range(len(nums):
            ans[i] = nums[nums[i]]
        return ans

C++

class Solution {
public:
    vector<int> buildArray(vector<int>& nums) {
        vector<int> ans(nums.size();
        for (int i = 0; i < nums.size(); ++i) {
            ans[i] = nums[nums[i]];
        }
        return ans;
    }
};

Сложность алгоритма по времени - O(N)

Так как в алгоритме происходит итерация по всем элементам массива, то сложность - O(N), то есть полный перебор каждого из элементов.

Сложность алгорима по памяти - O(N)

В принципе в задачах такого рода не принято считать, что переменная ans вносит свой вклад в оценку сложности алгоритма по памяти, так как ans - искомый объект. Однако в контексте данной задачи можно сказать, что сложность по памяти O(N), так как есть второй способ решения, в котором не требуется инициализаци нового объекта.

Способ 2

Данную задачу можно решить без дополнительных затрат на инициализацию нового объекта, меняя значения заданного массива “на ходу”. Трудность данного подхода состоит в том, что после первичного применения формулы ans[i] = nums[nums[i]] теряется старое значение, которое было в массиве до того, как его заменили. Решение “в лоб” здесь не сработает.

Например, у нас есть массив:

3	2	1	0

Мы начинаем итерироваться по нему в цикле от 0 до 4 (не включая 4), на первой итерации с i = 0 применяется формула: nums[0] = nums[nums[0]], то есть nums[0] становится nums[3] (т.е. нулем, так как nums[3] == 0).

Массив после первой итерации становится:

0	2	1	0

На второй итерации nums[1] становится равным 1, так как nums[nums[1]] == nums[2] == 1.

Массив после второй итерации:

0	1	1	0

Уже на третьей итерации (i = 2) проявляется ошибка. nums[2] = nums[nums[2]], то есть nums[2] = nums[1]. Проблема в том, что в оригинальном массиве nums[1] - это

2, а в текущем массиве nums[1] - это 1. Почему так получилось? Потому что в ходе первых двух итераций оригинальное значение nums[1] было потеряно.

Так, решение сводится к тому, чтобы каким-то образом в одной ячейке массива хранить как старое значение, так и новое.

Этого можно достичь, внимательно изучив ограничение задачи. Сказано, что 0 <= nums[i] < nums.length, а nums,length не может быть больше тысячи. Другими словами, любой элемент исходной перестановки всегда меньше 1000.

Так, алгоритм будет состоять из двух частей:

Итерация по всему массиву, в ходе которой к каждому элементу добавляется 1000 * (nums[nums[i]] % 1000)
Повторная итерация по всему массиву, в ходе которой значение каждого элемента делится нацело на 1000

Разберем подробно первый шаг. Вместо того, чтобы просто присваивать текущему элементу nums[i] значение nums[nums[i]], мы будем добавлять к нему остаток от деления nums[nums[i]] на 1000, то есть на каждой итерации nums[i] += 1000 * (nums[nums[i]] % 1000).

Здесь возникает три вопроса:

Почему мы прибавляем слагаемое, а не перезаписываем значение?
Почему nums[nums[i]] % 1000, а не просто nums[nums[i]]?
Зачем домножать на 1000?

Вопрос первый. Почему именно прибавляем? Это нужно как раз для того, чтобы в текущей ячейке массива сохранялось старое значение. Например, значение было 5, прибавив X, мы теперь знаем, что в ячейке лежит 5 + X (по идее X - это новое значение, но немного модифицированное). На втором шаге алгоритма нам достаточно убрать 5, чтобы получить искомое X.

Вопрос второй и третий. Зачем нужен остаток от деления, почему прибавляем такое странное слагаемое, еще и умноженное на 1000? Действительно, ведь любой элемент меньше 1000, значит и остаток от деления всегда будет равен элементу. Например, элемент равен 3, значит 3 % 1000 = 3, а если он равен 5, то 5 % 1000 = 5 и так далее. К тому же, мы этот остаток еще и домножаем на 1000. Как будто бы просто можно прибавлять 1000 * nums[nums[i]]. Это объясняется как раз тем, что в ходе предыдущих итераций значение массива могло быть модифицировано, а значит оригинальное значение могло быть снова потеряно.

Чтобы лучше понять, разберем еще один пример, отталкиваясь от противного. Есть массив:

5	0	1	2	3	4

Оттолкнемся от противного, будем добавлять просто 1000 * nums[nums[i]]. На 1-ой итерации к 5 мы прибавим просто 1000 * nums[nums[i]] (игнорируем остаток от деления на 1000). К 5 прибавяем 1000 * nums[5]. Тогда массив станет:

4005	0	1	2	3	4

Пока что самый первый элемент соответствует идее. Он “хранит” в себе как старое значение, так и новое. Старое - это остаток от деления на 1000 (5), а новое - это результат деления на 1000 нацело (4).

Но уже на 2-ой (i = 1) итерации вылезает ошибка. nums[nums[i]] равен 4005, а nums[1] пока что равен 0. Мы прибавляем к нему 1000 * 4005, в результате получаем 4005000. Это уже не соответствует идее хранения сразу двух чисел в одной ячейке: остаток от деления на 1000 равен 4005 (а хотелось бы иметь старое значение, то есть 0), результат деления на 1000 нацело тоже равен 4005 (а хотелось бы иметь 5).

Таким образом, формула 1000 * (nums[nums[i]] % 1000) применяется с целью сохранить старое значение в каждой ячейке массива ввиду его возможной потери при модификации массива налету, а также для получения нового путем деления на 1000 нацело.

Код:

python

class Solution:
    def buildArray(self, nums: List[int]) -> List[int]:
        n = len(nums)

        # Первый проход за O(N)
        for i in range(n):
            nums[i] += 1000 * (nums[nums[i]] % 1000)
            # nums[i] хранит старое и новое значение
            # старое - остаток от деления на 1000
            # новое - результат деления на 1000 нацело

        # Второй проход за O(N)
        for i in range(n):
            nums[i] //= 1000
        return nums

C++

class Solution {
public:
    vector<int> buildArray(vector<int>& nums) {
        int n = nums.size();

        // Первый проход за O(N)
        for (int i = 0; i < n; ++i) {
            nums[i] += 1000 * (nums[nums[i]] % 1000);
            // nums[i] хранит старое и новое значение
            // старое - остаток от деления на 1000
            // новое - результат деления на 1000 нацело
        }

        // Второй проход за O(N)
        for (int i = 0; i < n; ++i) {
            nums[i] /= 1000;
        }
        return nums;
    }
};

Сложность алгоритма по времени - O(N)

Для реализации достаточно дважды пробежаться по всему массиву целиком.

Сложность алгоритма по памяти - О(1)

Для решения данным способом не требуется никаких дополнительных объектов.