189rotateArray

发表于 | 更新于: |

题目原文
Rotate an array of n elements to the right by k steps.
For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

题目翻译
向右旋转转一个有n个元素的数组k步。比如：n = 7，k = 3时，数组 [1,2,3,4,5,6,7] 可以得到 [5,6,7,1,2,3,4] 。
注：尽量用多种方法来解决这个问题。

解题过程

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        list_1 = nums[-k:]
        list_2 = nums[:n-k]
        list_3 = list_1 + list_2
        return (list_3)

注意只能直接修改原数组，不能返回新的数组，修改必须是”in-place”的。

v0.2

1
2
3
4
5
6
7
n = len(nums)
      if k == 0:
          nums = nums
      elif k > 0 and k <= n:
          list_1 = nums[-k:]
          list_2 = nums[:n-k]
          nums = list_1 + list_2 # 这里错了，应该是nums[:]

This is not modifying nums in place. This is recreating a new list and reassigning the variable name of “nums” to it.

两个列表相连

  • 用“+”， list_3 = list_1+ list_2 这个是新建了一个list
  • 用extend 这个是在原list对象上操作

💡del不是nums.del(i)

​ 而是del nums[1]

continue和break要在for,while等循环中使用,单独的if语句中不能使用break和continue.

v0.3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        if k == 0:
            continue  # 这里报错 'continue' not properly in loop
        elif k > 0 and k <= n:
            list_1 = nums[:n-k]
            for i in range(n-k):
                del nums[i]
            nums.extend(list_1)
            return nums

v0.4

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def rotate(self, nums, k):
		n = len(nums)
        if k == 0:
            pass
        elif k > 0 and k <= n:
            list_1 = nums[:n-k]
            for i in range(n-k):
                del nums[i] # 问题出在这
            print(nums)
            nums.extend(list_1)
            return nums

Line 14: IndexError: list assignment index out of range

v1.0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def rotate(self, nums, k):
    """
    :type nums: List[int]
    :type k: int
    :rtype: void Do not return anything, modify nums in-place instead.
    """
    n = len(nums)
    if k == 0 :
        pass
    elif k > 0 and k <= n:
        list_1 = nums[:n-k]
        for i in nums[:n-k]:
            nums.remove(i)
        nums.extend(list_1)
    elif k > n:
        l = k % n
        list_1 = nums[:n-l]
        for i in nums[:n-l]:
            nums.remove(i)
        nums.extend(list_1)

if后面如果想什么也不做，可以用pass，后面看讨论知道，可以直接写个return，不返回任何值

我只想到这一种方法。

思路一

v1.1 讨论区里的答案，看完瞬间觉得自己好笨，我的想法不就是这个吗

1
2
3
n = len(nums)
       k = k % n
       nums[:] = nums[n-k:] + nums[:n-k]

list.insert(index, obj)

思路二

5.61%

1
2
for i in range(k):
	nums.insert(0, nums.pop())

思路三

切片

-3 % 5 = 2

74%

1
2
3
4
n = len(nums)
k = k % n
nums[:] = nums[n-k:] + nums[:n-k]
# nums[:] = nums[-k:] + nums[:-k]

这里有一点值得注意

1
nums[:] = nums[n-k:] + nums[:n-k]

不能写成这样

1
nums = nums[n-k:] + nums[:n-k]

前者能真正改变原来的nums，但后者仅仅能改变改变对一个新nums的引用，不是改变原来nums的值

可参考《Python编程》P58

思路四

Let the array be - 123456789 and k = 4

Step 1 - 12345 6789 —> 54321 6789

Step 2 - 54321 6789 —> 54321 9876

Step 3 - 543219876 —> 678912345

Classical 3-step array rotation:

  1. reverse the first n - k elements
  2. reverse the rest of them
  3. reverse the entire array
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def rotate(self, nums, k):
        if k is None or k <= 0:
            return
        k, end = k % len(nums), len(nums) - 1
        self.reverse(nums, 0, end - k)
        self.reverse(nums, end - k + 1, end)
        self.reverse(nums, 0, end)
        
    def reverse(self, nums, start, end):
        while start < end:
            nums[start], nums[end] = nums[end], nums[start]
            start, end = start + 1, end - 1

这里有个知识点我不清楚，就是一个类中一个函数可以调用另一个函数吗，怎么调用

思路五

实际上，为了使空间复杂度为O(1)，我们可能会想到对原数组做k次“循环右移一位”的解法。然而直接这么做会超时，所以可以考虑下面的优化做法。其思想是，每次把数组最后k位交换到正确的位置，循环直到所有元素位置正确。

1
2
3
4
5
6
7
8
9
10
11
12
def rotate(self, nums, k):
    """
    :type nums: List[int]
    :type k: int
    :rtype: void Do not return anything, modify nums in-place instead.
    """
    k, start, n = k % len(nums), 0, len(nums)
    while k % n != 0 and n > 0:
        for i in xrange(k):
            nums[start + i], nums[len(nums)-k+i] = nums[len(nums)-k+i], nums[start+i]
        start, n = start + k, n - k
        k = k % n

如果下次碰到这个题目应该怎么思考

  1. 直接brute force, 怎么简单怎么来，就是看到这个第一反应
  2. 然后写出后，分析它的算法和空间复杂度
  3. 然后优化，查找类的可以用字典来代替（优化的套路应该是有限的，只不过自己现在刚起步，碰到少）
  4. 最后想想有没有别的思路，如正反思考