LeetCode //189. Rotate Array-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode //189. Rotate Array。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

189. Rotate Array

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
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]

Example 2:

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

Constraints:

$1 <= nums.length <= 10^5$
$2^{31} <= nums[i] <= 2^{31} - 1$
$0 <= k <= 10^5$

From: LeetCode
Link: 189. Rotate Array
文章来源地址https://www.toymoban.com/news/detail-539749.html

Follow up:

Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
Could you do it in-place with O(1) extra space?

Solution:

Ideas：

1. We create a new dynamically allocated array that will hold the rearranged elements.

2. Then we iterate over the original array, placing each element on its new position in the new array. The new position is calculated as (i + k) % numsSize to ensure we wrap around to the start of the array when we reach the end.

3. We then copy the new array back into the original array.

4. Lastly, we free the memory we allocated for the new array.

This approach takes O(n) time because we’re doing a single pass from the array, and O(n) extra space to hold the rearranged elements.

Note: Please ensure your compiler supports C99 or later to use variable length arrays and the malloc, free function for dynamic memory allocation.

Code:

void rotate(int* nums, int numsSize, int k){
    int* newArr = malloc(numsSize * sizeof(int));

    for(int i = 0; i < numsSize; i++){
        newArr[(i + k) % numsSize] = nums[i];
    }

    for(int i = 0; i < numsSize; i++){
        nums[i] = newArr[i];
    }

    free(newArr);
}