0189. 轮转数组

0189. 轮转数组 #

  • 标签:数组
  • 难度:中等

题目大意 #

描述:给定一个数组 nums,再给定一个数字 k

要求:将数组中的元素向右移动 k 个位置。

说明

  • $1 \le nums.length \le 10^5$。
  • $-2^{31} \le nums[i] \le 2^{31} - 1$。
  • $0 \le k \le 10^5$。
  • 使用空间复杂度为 O(1) 的原地算法解决这个问题。

示例

1
2
3
4
5
6
输入    nums = [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]

解题思路 #

思路 1: #

可以用一个新数组,先保存原数组的后 k 个元素,再保存原数组的前 n - k 个元素。但题目要求不使用额外的数组空间,那么就需要在原数组上做操作。

我们可以先把整个数组翻转一下,这样后半段元素就到了前边,前半段元素就到了后边,只不过元素顺序是反着的。我们再从 k 位置分隔开,将 [0...k - 1] 区间上的元素和 [k...n - 1] 区间上的元素再翻转一下,就得到了最终结果。

具体步骤:

  1. 将数组 [0, n - 1] 位置上的元素全部翻转。
  2. 将数组 [0, k - 1] 位置上的元素进行翻转。
  3. 将数组 [k, n - 1] 位置上的元素进行翻转。

思路 1:代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        k = k % n
        self.reverse(nums, 0, n-1)
        self.reverse(nums, 0, k-1)
        self.reverse(nums, k, n-1)
    def reverse(self, nums: List[int], left: int, right: int) -> None:
        while left < right :
            tmp = nums[left]
            nums[left] = nums[right]
            nums[right] = tmp
            left += 1
            right -= 1https://lestore.lenovo.com/detail/25113
本站总访问量  次  |  您是本站第  位访问者