Ссылка на задачу: https://leetcode.com/problems/concatenation-of-array/description/?envType=problem-list-v2&envId=array
Дан массив целых чисел длины n, вам нужно создать массив ans длины 2n, где ans[i] == nums[i] и ans[i + n] == nums[i] для 0 <= i < n. Массив является 0-indexed.
Другими словами, ans - это конкатенация двух массивов nums.
Верните ans в ответе.
0-indexed означает то, что индексация элементов в массиве начинается с нуля.
Input:
| 1 | 2 | 1 |
|---|
Output:
| 1 | 2 | 1 | 1 | 2 | 1 |
|---|
Input:
| 1 | 3 | 2 | 1 |
|---|
Output:
| 1 | 3 | 2 | 1 | 1 | 3 | 2 | 1 |
|---|
n == nums.length
1 <= n <= 1000
1 <= nums[i] <= 1000
Данный способ предполагает решение “в лоб”. Суть кроется в описании: необходимо вернуть в ответе конкатенацию двух массивов nums. Язык python предоставляет разработчику такой функционал “из коробки”.
Алгоритм:
Код:
class Solution:
def getConcatenation(self, nums: List[int]) -> List[int]:
return nums + numsСложность алгоритма по времени - O(N)
Почему O(N), ведь никаких явных итераций по массиву здесь нет? Дело в том, что в python-коде, действительно, нет никаких явных инструкций, отвечающих за итерацию, но они есть в байт-коде, в который транслируется python-код.
Это можно пронализировать, используя пакет dis:
import dis
from typing import List
def getConcatenation(self, nums: List[int]) -> List[int]:
'''
Вынесли функцию отдельно для анализа
'''
return nums + nums
if __name__ == "__main__":
dis.dis(getConcatenation)Функция dis пакета dis покажет список используемых инструкций:
4 0 RESUME 0
8 2 LOAD_FAST 1 (nums)
4 LOAD_FAST 1 (nums)
6 BINARY_OP 0 (+)
10 RETURN_VALUEНам интересна секция 8, шаги 2, 4 и 6. Сначала дважды используется LOAD_FAST (низкоуровневая операци загрузки данных в регистры процессора), то есть выделяется память под две локальные переменные точно такого же размера, как и nums (размера n). Затем выполняется операция BINARY_OP, в которой как раз и кроется сложность O(N).
Сложность алгоритма по памяти - O(N)
В шагах 2 и 4 секции 8 дважды используется LOAD_FAST, где выделяется память под две локальные переменные размера n, то есть задействуется 2n памяти, значит сложность - O(N).
Примечание: в принципе это можно не относить к сложности алгоритма, так как программисту в любом случае для решения задачи потребуется дополнительная память, чтобы вернуть в ответе ans. Очень часто в задачах на leetcode не принято брать во внимание ту память, что необходима для создания искомого объекта.
Здесь точно такое же решение “в лоб”, но с учетом хорошего тона C++. Если заранее известен размер массива, то лучше выделить память под него сразу, а затем в ходе итерации присваивать каждому элементу его конкретное значение, нежели чем пользоваться push_back и тратить время компилятора на дополнительную реаллокацию.
Алгоритм:
Аллокация памяти под ans заранее известного размера 2n
Итерация от 0 до n и присваивание элементов ans
Код:
class Solution {
public:
vector<int> getConcatenation(vector<int>& nums) {
vector<int> ans(2 * nums.size());
for (int i = 0; i < nums.size(); ++i) {
ans[i] = nums[i];
ans[i + nums.size()] = nums[i];
}
return ans;
}
};Сложность алгоритма по времени - O(N)
Здесь идет проход по всем элементам от 0 до n
Сложность алгоритма по памяти - O(N)
Инициализация ans размером 2 * nums.size(). Опять-таки, данной сложностью часто пренебрегают, когда разговаривают о сложности на интервью, так как в этой задаче испытуемому в любом случае потребуется дополнительная память для ans.