Ссылка на задачу: https://leetcode.com/problems/shuffle-the-array/description/
Дан массив nums, состоящий из 2n элементов в формате [x1,x2,…,xn,y1,y2,…,yn].
Необходимо вернуть массив в формате [x1,y1,x2,y2,…,xn,yn].
Input: n = 3
| 2 | 5 | 1 | 3 | 4 | 7 |
|---|
Output:
| 2 | 3 | 5 | 4 | 1 | 7 |
|---|
Объяснение: x1 = 2, x2 = 5, x3 = 1; y1 = 3, y2 = 4, y3 = 7, поэтому x1,y1,x2,y2,x3,y3 - это [2, 3, 5, 4, 1, 7]
Input: n = 4
| 1 | 2 | 3 | 4 | 4 | 3 | 2 | 1 |
|---|
Output:
| 1 | 4 | 2 | 3 | 3 | 2 | 4 | 1 |
|---|
Input: n = 2
| 1 | 1 | 2 | 2 |
|---|
Output:
| 1 | 2 | 1 | 2 |
|---|
1 <= n <= 500
nums.length == 2n
1 <= nums[i] <= 10^3
В более простом случае мы можем инициализировать дополнительный массив размером 2n, чтобы присваивать его элементам нужные значения. В исходном массиве первая половина - это «иксы», вторая - «игреки». Нам же требуется сделать так, чтобы в результирующем иксы и игреки чередовались друг за другом.
Так, достаточно пробежаться по массиву двумя указателями, один взят для «иксов», второй - для «игреков». В результирующий мы будем подкладывать значения по очереди: сначала с помощью первого указателя («иксы»), затем второго («игреки»).
Алгоритм:
Инициализировать дополнительный массив ans размером 2n и индекс k для присваивания значений ans
Пробежаться по заданному массиву nums в диапазоне индексов от 0 до n (индекс i)
k-тому элементу ans присвоить nums[i], инкрементировать k (это «иксы»)
k-тому элементу ans присвоить уже nums[i + n] (это «игреки»)
Примечание: с точки зрения написания кода нам не нужно заводить две разных переменных под два разных указателя; первый указатель - это i, второй - i + n
Код:
python
class Solution:
def shuffle(self, nums: List[int], n: int) -> List[int]:
ans = [-1] * 2 * n
k = 0
for i in range(n):
ans[k] = nums[i]
k += 1
ans[k] = nums[i + n]
k += 1
return ansC++
class Solution {
public:
vector<int> shuffle(vector<int>& nums, int n) {
vector<int> ans(2 * n);
int k = 0;
for (int i = 0; i < n; ++i) {
ans[k++] = nums[i];
ans[k++] = nums[i + n];
}
return ans;
}
};Сложность алгоритма по времени - O(N)
Для реализации достаточно пробежаться вдоль исходного массива nums размером 2n всего один раз.
Сложность алгоритма по памяти - O(N)
Почему O(N), ведь результат, который требуется вернуть в задаче, не должен вносить вклада в оценку сложности? Все дело в том, что в задаче требуется модифицировать исходный массив, а не составить новый на базе исходного. Так, массив ans здесь выступает в роли дополнительного объекта.
Можно ли нам каким-либо образом модифицировать исходный массив “на лету”?
У “иксов” индексы от 0 до n. После перестановки индекс каждого “икса” является четным, а “игрека” - нечетным.
Первые n элементов - “иксы”, остальные n - “игреки”. Так, мы снова можем заранее инициализировать указатель для “иксов” (i в диапазоне от 0 до n) и “игреков” (j в диапазоне от n до 2n), а в рамках одного перебора всех 2n элементов заданного массива присваивать либо по i (если текущий индекс перебора четный), либо по j (если текущий индекс перебора нечетный).
Проблема в том, что после присвоения элементу заданного массива уже с индексом 1 мы потеряем его старое значение.
Пример: [1,2,3,4,11,12,13,14], n = 4. Первый элемент имеет четный индекс 0, поэтому ему мы присваиваем значение по указателю i, то есть та же 1 (i теперь становится 1). Следующий элемент имеет уже нечетный индекс 1, поэтому ему нужно присвоить значение по j, то есть 11 (j теперь стал n + 1). После данных двух модификаций массив стал: [1,11,3,4,11,12,13,14].
Дальше у нас на рассмотрении элемент с индексом 2, снова четный, поэтому и присвоить нужно по i, который равен 1. Однако теперь, обратившись к массиву по индексу 1, мы увидим там 11, а не 2, как было раньше. Проблема кроется в том, что мы потеряли старое значение.
Задача сводится к вопросу: можно ли каким-то образом в одной ячейке массива хранить как старое значение, так и новое?
Да, можно. Это достигается путем использования “трюков"" с умножением и остатком от деления. На каждой итерации к элементу необходимо добавить слагаемое 1001 * (nums[index] % 1001). Почему именно такое слагаемое? Более подробно ответ на этот вопрос описан в задаче 1920 (https://leetcode.com/problems/build-array-from-permutation/description/). Приводить его здесь мы не будем, иначе способ 2 станет слишком огромен.
Алгоритм:
Инициализировать два указателя: i с начальным значением 0 и j с начальным значением n
Перебрать все элементы заданного массива индексом k
На каждой итерации, где k кратен 2, прибавить к элементу исходного массива слагаемое 1001 * (nums[i] % 1001)
На каждой итерации, где k не кратен 2, прибавить 1001 * (nums[j] % 1001)
Перебрать все элементы исходного и уже модифицированного массива еще раз
На каждой итерации разделить элемент нацело на 1001
Код:
python
class Solution:
def shuffle(self, nums: List[int], n: int) -> List[int]:
i = 0
j = n
for k in range(2 * n):
if k % 2 == 0:
nums[k] += 1001 * (nums[i] % 1001)
i += 1
else:
nums[k] += 1001 * (nums[j] % 1001)
j += 1
for k in range(2 * n):
nums[k] //= 1001
return numsC++
class Solution {
public:
vector<int> shuffle(vector<int>& nums, int n) {
int i = 0;
int j = n;
for (int k = 0; k < 2 * n; ++k) {
if (k % 2 == 0) {
nums[k] += 1001 * (nums[i++] % 1001);
} else {
nums[k] += 1001 * (nums[j++] % 1001);
}
}
for (int k = 0; k < 2 * n; ++k) {
nums[k] /= 1001;
}
return nums;
}
};Сложность алгоритма по времени - O(N)
Реализация сводится к двум полным переборам исходного массива размером 2n, значит сложность O(2N + 2N), константа выносится, результирующая сложность - O(N).
Сложность алгоритма по памяти - O(1)
В данном подходе мы не выделяем дополнительный массив, а работаем с исходным. Память под два целочисленных указателя не зависит от размера входных данных.