加米，请大家帮看一下189. Rotate Array, python里pass by reference的细节

大家好

题目lc189,rotate array有一点python 3细节上的疑问，请大家帮忙看看，会尽力加米。

1. Given an array, rotate the array to the right by k steps, where k is non-negative.
   
2. 
   
3. Example 1:
   
4. 
   
5. Input: nums = [1,2,3,4,5,6,7], k = 3
   
6. Output: [5,6,7,1,2,3,4]
   
7. Explanation:
   
8. rotate 1 steps to the right: [7,1,2,3,4,5,6]
   
9. rotate 2 steps to the right: [6,7,1,2,3,4,5]
   
10. rotate 3 steps to the right: [5,6,7,1,2,3,4]

复制代码

我的答案和思路：
将给定list全部reverse一遍，再分别reverse前k个数，后（n-k)个数，就达到了分段rotate的目的。

我的问题，这段代码运行出来
Solution.rotate([1,2,3,4,5,6], 3) 结果是[6,5,4,3,2,1]。debug发现self.reverse(nums[:k])， self.reverse(nums[k:])运行后，nums不会发生改变。nums是mutable param, 传入function的param的改变不是应该同步吗？而且为什么self.reverse(nums)就可以实现nums的内容update？

1. class wrong_Solution:
   
2.     def rotate(self, nums: List[int], k: int) -> None:
   
3.     """
   
4.     Do not return anything, modify nums in-place instead.
   
5.     """
   
6.         self.reverse(nums)
   
7.         self.reverse(nums[:k])
   
8.         self.reverse(nums[k:])
   
9.         
   
10.     def reverse(self, nums):
    
11.         left, right = 0, len(nums) - 1
    
12.         while left <= right:
    
13.             nums[left], nums[right] = nums[right], nums[left]
    
14.             left += 1
    
15.             right -= 1

复制代码

1. right solution
   
2. 
   
3. class Solution:
   
4.     # I Love Yahoo solution; O(n) O(1)
   
5.     def reverse(self, nums: list, start: int, end: int) -> None:
   
6.         while start < end:
   
7.             nums[start], nums[end] = nums[end], nums[start]
   
8.             start, end = start + 1, end - 1
   
9. 
   
10.     def rotate(self, nums: List[int], k: int) -> None:
    
11.         #ATTENTION: without L12, l16 would return out of range error.
    
12.         n = len(nums)
    
13.         k %= n
    
14. 
    
15.         self.reverse(nums, 0, n - 1)
    
16.         self.reverse(nums, 0, k - 1)
    
17.         self.reverse(nums, k, n - 1)
    

复制代码

nums[:k] 和nums[k:]产生新的数组了。你可以把reverse函数改下，传nums数组和left, right 两个index

直接用2 pointer 做会简单很多，还不需要多用reverse 的space。

zhimingli123 发表于 2021-10-11 13:37
直接用2 pointer 做会简单很多，还不需要多用reverse 的space。

hi, reverse没有开辟新的space吧？而且我觉得reverse就是用2 pointer？可以贴你的思路吗？谢谢

class Solution:
    def rotate(self, nums, k):
        n = len(nums)
        k = k % n
        
        count = 0 # number of values rotated
        
        start = 0 # starting pointer
        while count < n:
            pointer = start
            prev = nums[pointer]
            while True:
                count += 1
               
                # store the next value
                next_idx = (pointer + k) % n
               
                next_value = nums[next_idx]
               
                # set the previous value to the rotate place
                nums[next_idx] = prev
               
                # store the current value for next rotation
                prev = next_value
               
                pointer = next_idx
               
                if pointer == start:
                    break
            start += 1

基本就是放一个starting pointer，然后从这个starting pointer k 个k个往后看，然后当你回到这个starting pointer 之后，就看下一个就行了. recursion 的问题是recursion本身就需要space因为是stack recursion，所以不能算是O（1）

fropen 发表于 2021-10-11 14:47
nums[:k] 和nums[k:]产生新的数组了。你可以把reverse函数改下，传nums数组和left, right 两个index

1. a = [1,2,3,4,5,6,7]
   
2. a[:3]
   
3. [1, 2, 3]
   
4. a[:3] = [4,5,6]
   
5. a
   
6. [4, 5, 6, 4, 5, 6, 7]
   

复制代码

谢谢，不过我对array slice感觉很困惑。。。如果Slicing the list will create a new list with the sliced contents，那我上面贴的这一小段代码，感觉是change in place, not create a new list?

超人96825 发表于 2021-10-11 16:06
谢谢，不过我对array slice感觉很困惑。。。如果Slicing the list will create a new list with the slic ...

我说的不是很准确, 我是这样理解的：
nums 数组保存的不是数字本身，而是references，像这样：[one, two, three]，
nums[1:] 的结果是 [two, three]，我们可以给他起个名字nums2（传给函数的时候就是那个形参nums)，反转nums2的结果是 [three, two]，这个结果并不会影响nums本身，nums本身还是[one, two, three]。我们可以任意给nums2赋值，让它指向5，6，改变的只是nums2[0]，nums2[1] 指向的东西。
这就和如下类似：
aa = 10
bb = aa
bb = 20
now, aa = ? (aa 的值显然不会变)

你的这段代码是另外一个东西了，叫slice assignment（感觉理解起来要难多了）。参考：https://stackoverflow.com/questi ... rk-with-list-slices

可以用id来打印一下reference，印证：
In [25]: a = [1, 2, 3]
In [26]: b = a[1:]
In [27]: id(a[1]), id(a[2]), id(b[0]), id(b[1])
Out[27]: (4307679568, 4307679600, 4307679568, 4307679600)
In [28]: tmp = b[0]
In [29]: b[0] = b[1]
In [30]: b[1] = tmp
In [31]: id(a[1]), id(a[2]), id(b[0]), id(b[1])
Out[31]: (4307679568, 4307679600, 4307679600, 4307679568)

个人理解，如果错误请见谅。

fropen 发表于 2021-10-11 17:21
我说的不是很准确, 我是这样理解的：
nums 数组保存的不是数字本身，而是reference ...

谢谢，非常清晰！！！！