Activity

1. lyonyang

   added

   数组

   on Jul 26, 2021
2. zhangke666163 commented on Jul 29, 2021

   

   zhangke666163

   on Jul 29, 2021

   More actions

   思路：复制一个新数组，将旧数组元素右移K个位置，替换到新数组对应位置，注意移动时数组越界问题。
   时间、空间复杂度：O(n)
   代码：

   import copy
   def array_right(nums, k):
       k = k % len(nums)
       # k等于数组长度时，元素位置不会改变，输出原数组即可
       if k == 0:
           return nums
       new_array = copy.deepcopy(nums)
       for i in range(len(nums)):
           if i+k < len(nums):
               # 数组下标未越界
               new_array[i+k] = nums[i]
           else:
               # 数组下标越界
               new_array[i+k-len(nums)] = nums[i]
       return new_array
   
   if __name__ == '__main__':
       print(array_right([1,2,3,4,5,6,7], 3))
   
   
3. chuchumeme commented on Jul 29, 2021

   

   chuchumeme

   on Jul 29, 2021

   More actions

   方法一：（通过了）

   思路:

   循环每一项，根据k值旋转放入新数组，再把新数组循环赋值给nums

   复杂度

   时间复杂度: 0(n) 空间复杂度: O(n)

   代码:

   const len = nums.length;
   const arr = [];
   for (let i = 0; i < len; i++) {
       arr[(i + k) % len] = nums[i];
   }
   for (let i = 0; i < len; i++) {
       nums[i] = arr[i];
   }
   

   方法二：（没过，超出时间限制）

   思路:

   通过while循环，将k减到0则旋转完成，数组进行弹出和插入

   复杂度

   时间复杂度: 0(n) 空间复杂度: O(n)

   代码：

   while(k > 0) {
     nums.unshift(nums.pop());
     k--;
   }
   

   为啥超出时间限制了。。
4. xuezc1119 commented on Jul 29, 2021

   

   xuezc1119

   on Jul 29, 2021

   More actions

   方法一

   思路

   通过给定的k将数组分成两部分
   将这两部分逆向拼接起来

   复杂度

   时间复杂度O(n)，空间复杂度O(n)

   代码

   /**
    * @param {number[]} nums
    * @param {number} k
    * @return {void} Do not return anything, modify nums in-place instead.
    */
    var rotate = function(nums, k) {
     nums.push(...nums.splice(0, nums.length - k % nums.length)); // 删除前半段，取后半段,两者拼接
   };

   方法二

   思路

   通过k确定数组第一位到最后一位的新位置
   剩余的数据前移

   复杂度

   时间复杂度O(n)，空间复杂度O(n)

   代码

   /**
    * @param {number[]} nums
    * @param {number} k
    * @return {void} Do not return anything, modify nums in-place instead.
    */
   var rotate = function(nums, k) {
       let index = k % nums.length;
       console.log(index);
       if (index > 0) { // 等于0不移动
           let temp = JSON.parse(JSON.stringify(nums));
           for (let i = 0; i < index; i++) { // 前移数据
               nums[index - i - 1] = temp[temp.length - 1 - i]; // 倒着赋值
           }
           for (let i = index; i < nums.length; i++) { // 后移数据
               nums[i] = temp[i - index];
           }
       }
   };
5. lyonyang

   added

   第1周

   第二周

   中等

   and removed

   第二周

   on Aug 7, 2021
6. lyonyang commented on Aug 7, 2021

   

   lyonyang

   on Aug 7, 2021

   MemberAuthor

   More actions

   思路一 - 切片拼接

   以倒数第 k 位置为分界线 , 用切片切分出两个数组 , 再拼接两个数组 , 由于要求在原地操作所以最后再进行一下复制 (但是这样的话空间复杂度为 $O(N)$ 而不是 $O(1)$)

   注意 : k 可能大于数组长度

   class Solution:
       def rotate(self, nums: List[int], k: int) -> None:
           """
           Do not return anything, modify nums in-place instead.
           """
           nums[:] = nums[len(nums) - k % len(nums):] + nums[:len(nums) - k % len(nums)]

   时间复杂度：$O(N)$ , N 为数组长度

   空间复杂度：$O(N)$

   思路二 - 环形换位

   向右移动 k 个位置 , 或者是向左移动 nums.length - k 个位置

   向左换位 : 从尾部开始遍历 , 将第 i 个元素与第 i - nums.length - k 个元素互换 , 互换之前需要将被互换的位置的元素用变量存储起来再作为下一个换位的元素继续重复操作 , 整个换位过程刚好形成一个环

   向右换位 : 从头部开始遍历 , 将第 i 个元素与第 i + k 个元素互换 , 互换之前同样需要将被互换的位置的元素用变量存储起来再作为下一个换位的元素继续重复操作 , 整个换位过程刚好形成一个环

   注意 :

   • k 可能大于数组长度
   • k % len(nums) == 0 表示数组不移动
   • 换位过程中可能有多个环 , 所以如果没有遍历完 , 当下一个索引回到了开始索引时 , 就应该往后挪一位继续换位操作

   # 以右移为例
   class Solution:
       def rotate(self, nums, k) -> None:
           """
           Do not return anything, modify nums in-place instead.
           """
           if k % len(nums) == 0: return
           start, index, next_num = 0, 0, nums[0]
           for i in range(len(nums)):
               next_index = (index + k) % len(nums)
               next_num, nums[next_index] = nums[next_index], next_num
               index = next_index
               if next_index == start:
                   index = start = start + 1
                   next_num = nums[index]

   时间复杂度：$O(N)$ , N 为数组长度

   空间复杂度：$O(1)$

   思路三 - 三次反转

   向右移 k 个位置 , 就是把从 len(nums) - k 到 len(nums) -1 的这段数组 , 与从 0 到 len(nums) - k - 1 这段数组调换一下位置 , 那我们可以 :

   1. 先反转整个数组 , 使两段数组的位置正确
   2. 但是由于反转了整个数组 , 所以两段数组的位置顺序都被反转了 , 那么我们再分别反转这两段数组

   class Solution:
       def rotate(self, nums, k) -> None:
           """
           Do not return anything, modify nums in-place instead.
           """
           self.reverse(0, len(nums) - 1, nums)
           self.reverse(0, k % len(nums) - 1, nums)
           self.reverse(k % len(nums), len(nums) - 1, nums)
   
       def reverse(self, start, end, nums):
           for i in range((end - start + 1) // 2):
               nums[start + i], nums[end - i] = nums[end - i], nums[start + i]

   时间复杂度：$O(N)$ , N 为数组长度

   空间复杂度：$O(1)$