本文主要是介绍leetcode:189.旋转数组,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
问题描述:
189. 旋转数组
给定一个数组,将数组中的元素向右移动k
个位置,其中k
是非负数。
示例 1:
输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释: 向右旋转 1 步: [7,1,2,3,4,5,6],向右旋转 2 步: [6,7,1,2,3,4,5],向右旋转 3 步: [5,6,7,1,2,3,4]
说明:
- 尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。
- 要求使用空间复杂度为
O(1)
的原地算法
问题分析:
这个问题出现在好未来图像面试上当时想的是第三个笨方法。面试时出的是向左移动k个数。
方法一:使用Python
切片操作,切开,颠倒,组合,完成。
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)nums[:] = nums[n-k:] + nums[:n-k]if __name__ == "__main__":test = Solution()nums = [1,2,3,4,5,6,7]test.rotate(nums, 3)print(nums)
方法二:把这个 nums
翻转, 然后再把对应的两个小区间翻转。(这方法也可以用Python
中的nums[::-1]
实现)
class Solution:def reverse(self, nums, start, end):while start < end:nums[start], nums[end] = nums[end], nums[start]start, end = start + 1, end - 1def 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)self.reverse(nums, 0, n - 1)self.reverse(nums, 0, k - 1)self.reverse(nums, k, n - 1)
方法三:最简单的想法,进行k次循环,每次循环转移所有元素。时间复杂度O(n*k) 、空间复杂度O(1)
class Solution:def rotate(self, nums, k):nums_len = len(nums)while k > 0:k-=1previous = nums[nums_len-1]for j in range(nums_len):nums[j], previous = previous, nums[j]
方法四:我们可以直接将阵列的每个数字放置在所需的正确位置。但如果我们这样做,我们将破坏原始元素。因此,我们需要将被替换的数字存储在temptemp变量中。然后,我们可以将替换的数字(temptemp)放在正确的位置。时间复杂度O(n) 、空间复杂度O(1)
def rotate(self, nums, k):count = 0start = 0nums_len = len(nums)while count<nums_len:current = startprev = nums[start]next = (current+k) % nums_lenprev, nums[next] = nums[next], prev current = nextcount+=1while start!=current:next = (current+k) % nums_lenprev, nums[next] = nums[next], prev current = nextcount+=1start += 1
题目链接:leetcode-cn.com/problems/rotate-array/description/
参考:https://blog.csdn.net/XX_123_1_RJ/article/details/82905287
这篇关于leetcode:189.旋转数组的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!