Этот код сначала перебирает список чисел, обновляя количество целых чисел 0, 1, 2, также называемых красным, белым и синим соответственно. nums гарантированно будет содержать только целые числа 0, 1 и/или 2. После нахождения счетчиков код использует [::], трюк для изменения списка на месте, для сортировки nums.
Код: Выделить всё
def sortColors(self, nums: List[int]) -> None:
red = white = blue = 0
for num in nums:
match num:
case 0:
red += 1
case 1:
white += 1
case 2:
blue += 1
# [::] to modify nums in-place - Space O(1)
nums[::] = ([0] * red) + ([1] * white) + ([2] * blue)
return nums
Я думал, что ([0] * красный) + ([1] * белый) + ([2] * синий) будет оцениваться перед изменением чисел, то есть этот список необходимо будет создать и сохранить в памяти, прежде чем nums[::] = сможет продолжить работу. На мой взгляд, это имеет смысл, поскольку в Python правая часть = оценивается перед присвоением переменной, поэтому такие вещи, как x = x + 1, работают. Таким образом, согласно этому пониманию, на этом этапе кода как исходный список nums, так и новый список будут храниться в памяти. Поскольку новый список будет иметь ту же длину, что и nums, потребуется дополнительное пространство O(n).
Однако инструмент анализатора сообщил, что этот код занимает пространство O(1) . Единственное, о чем я могу думать, это то, что в момент вызова nums[::] = код игнорирует исходное содержимое nums и изменяет nums на месте в новый список.
Каково это пространство O(1) и правильно ли я понимаю сложность пространства и назначение переменных?
Подробнее здесь:
https://stackoverflow.com/questions/788 ... ist1-list2