Nav: << previous: 188.买卖股票的最佳时机 IV | next: 190.颠倒二进制位 >>
Description
tab: English
<p>Given an integer array <code>nums</code>, rotate the array to the right by <code>k</code> steps, where <code>k</code> is non-negative.</p>
<p> </p>
<p><strong class="example">Example 1:</strong></p>
<pre>
<strong>Input:</strong> nums = [1,2,3,4,5,6,7], k = 3
<strong>Output:</strong> [5,6,7,1,2,3,4]
<strong>Explanation:</strong>
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]
</pre>
<p><strong class="example">Example 2:</strong></p>
<pre>
<strong>Input:</strong> nums = [-1,-100,3,99], k = 2
<strong>Output:</strong> [3,99,-1,-100]
<strong>Explanation:</strong>
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]
</pre>
<p> </p>
<p><strong>Constraints:</strong></p>
<ul>
<li><code>1 <= nums.length <= 10<sup>5</sup></code></li>
<li><code>-2<sup>31</sup> <= nums[i] <= 2<sup>31</sup> - 1</code></li>
<li><code>0 <= k <= 10<sup>5</sup></code></li>
</ul>
<p> </p>
<p><strong>Follow up:</strong></p>
<ul>
<li>Try to come up with as many solutions as you can. There are at least <strong>three</strong> different ways to solve this problem.</li>
<li>Could you do it in-place with <code>O(1)</code> extra space?</li>
</ul>
> [!tip]- Hint 1
>
> The easiest solution would use additional memory and that is perfectly fine.
> [!tip]- Hint 2
>
> The actual trick comes when trying to solve this problem without using any additional memory. This means you need to use the original array somehow to move the elements around. Now, we can place each element in its original location and shift all the elements around it to adjust as that would be too costly and most likely will time out on larger input arrays.
> [!tip]- Hint 3
>
> One line of thought is based on reversing the array (or parts of it) to obtain the desired result. Think about how reversal might potentially help us out by using an example.
> [!tip]- Hint 4
>
> The other line of thought is a tad bit complicated but essentially it builds on the idea of placing each element in its original position while keeping track of the element originally in that position. Basically, at every step, we place an element in its rightful position and keep track of the element already there or the one being overwritten in an additional variable. We can't do this in one linear pass and the idea here is based on <b>cyclic-dependencies</b> between elements.
---
[submissions](https://leetcode.com/problems/rotate-array/submissions/) | [solutions](https://leetcode.com/problems/rotate-array/solutions/)
tab: 中文
<p>给定一个整数数组 <code>nums</code>，将数组中的元素向右轮转 <code>k</code><em> </em>个位置，其中 <code>k</code><em> </em>是非负数。</p>
<p> </p>
<p><strong>示例 1:</strong></p>
<pre>
<strong>输入:</strong> nums = [1,2,3,4,5,6,7], k = 3
<strong>输出:</strong> <code>[5,6,7,1,2,3,4]</code>
<strong>解释:</strong>
向右轮转 1 步: <code>[7,1,2,3,4,5,6]</code>
向右轮转 2 步: <code>[6,7,1,2,3,4,5]
</code>向右轮转 3 步: <code>[5,6,7,1,2,3,4]</code>
</pre>
<p><strong>示例 2:</strong></p>
<pre>
<strong>输入：</strong>nums = [-1,-100,3,99], k = 2
<strong>输出：</strong>[3,99,-1,-100]
<strong>解释:</strong>
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]</pre>
<p> </p>
<p><strong>提示：</strong></p>
<ul>
<li><code>1 <= nums.length <= 10<sup>5</sup></code></li>
<li><code>-2<sup>31</sup> <= nums[i] <= 2<sup>31</sup> - 1</code></li>
<li><code>0 <= k <= 10<sup>5</sup></code></li>
</ul>
<p> </p>
<p><strong>进阶：</strong></p>
<ul>
<li>尽可能想出更多的解决方案，至少有 <strong>三种</strong> 不同的方法可以解决这个问题。</li>
<li>你可以使用空间复杂度为 <code>O(1)</code> 的 <strong>原地 </strong>算法解决这个问题吗？</li>
</ul>
> [!tip]- 提示 1
>
> The easiest solution would use additional memory and that is perfectly fine.
> [!tip]- 提示 2
>
> The actual trick comes when trying to solve this problem without using any additional memory. This means you need to use the original array somehow to move the elements around. Now, we can place each element in its original location and shift all the elements around it to adjust as that would be too costly and most likely will time out on larger input arrays.
> [!tip]- 提示 3
>
> One line of thought is based on reversing the array (or parts of it) to obtain the desired result. Think about how reversal might potentially help us out by using an example.
> [!tip]- 提示 4
>
> The other line of thought is a tad bit complicated but essentially it builds on the idea of placing each element in its original position while keeping track of the element originally in that position. Basically, at every step, we place an element in its rightful position and keep track of the element already there or the one being overwritten in an additional variable. We can't do this in one linear pass and the idea here is based on <b>cyclic-dependencies</b> between elements.
---
[提交记录](https://leetcode.cn/problems/rotate-array/submissions/) | [题解](https://leetcode.cn/problems/rotate-array/solution/)
Solutions & Notes
properties:
note.updated:
displayName: Last Updated
note.relative_links:
displayName: Related Links
note.desc:
displayName: Description
note.grade:
displayName: Rating
note.program_language:
displayName: Language
note.time_complexity:
displayName: TC
note.space_complexity:
displayName: SC
views:
- type: table
name: Solutions & Notes
filters:
and:
- file.hasLink(this.file)
- file.tags.containsAny("leetcode/solution", "leetcode/note")
order:
- file.name
- desc
- program_language
- time_complexity
- space_complexity
- grade
- relative_links
- updated
sort:
- property: grade
direction: ASC
- property: time_complexity
direction: ASC
- property: program_language
direction: ASC
columnSize:
file.name: 104
note.space_complexity: 65
note.grade: 126
Similar Problems
properties:
note.lcTopics:
displayName: Topics
note.lcAcRate:
displayName: AC Rate
note.favorites:
displayName: Favorites
note.grade:
displayName: Rating
note.translatedTitle:
displayName: Title (CN)
note.lcDifficulty:
displayName: Difficulty
views:
- type: table
name: Similar Problems
filters:
and:
- file.hasLink(this.file)
- similarQuestions.contains(this.file)
order:
- file.name
- translatedTitle
- lcTopics
- lcDifficulty
- lcAcRate
- grade
- favorites
sort:
- property: file.name
direction: ASC
- property: lcTopics
direction: DESC
columnSize:
note.translatedTitle: 240
note.lcTopics: 347
note.lcAcRate: 75
note.grade: 122