3种方法解轮转数组

题目描述：给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

例如

输入: 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]

我想到的第一种方法就是暴力选择 时间复杂度O(k*N)

当没有明确说明k 的值 根据最坏情况原则 它的时间复杂度 应为 O(N^2)

那么结果毫无悬念 结果又超出了 时间的限制。下面是我的代码 简单易于理解 就不多解释了；

void rotate(int* nums, int numsSize, int k){
    int i = 0;
    int j = 0;
    for (i = 0; i < k; i++)
    {
        int tmp = nums[numsSize - 1];
        for (j = numsSize-1; j > 0; j--)
        {
            nums[j] = nums[j - 1];
        }
        nums[0] = tmp;
    }
    return nums;
}

1.使用额外的数组

以额外的空间换取时间；开辟额外的数组 进行存储。

void rotate(int* nums, int numsSize, int k){
    int arr[100000] = {0};
    int i = 0;
    k %= numsSize;
    for(i = 0;i<k;i++)
    {
        arr[i] = nums[numsSize-k+i];
    }
    for(i = k;i<numsSize;i++)
    {
        arr[i] = nums[i-k];
    }
    for(i = 0;i<numsSize;i++)
    {
        nums[i] = arr[i];
    }
    return nums;
}

2.反转数组的方法

三次反转 

例如

数组             1 2 3 4 5 6 7  k = 3

第一步反转  7 6 5 4 3 2 1

第二步反转  5 6 7 4 3 2 1

第三步反转  5 6 7 4 1 2 3

void swap(int* a, int* b) {
    int t = *a;
    *a = *b, *b = t;
}

void reverse(int* nums, int start, int end) {
    while (start < end) {
        swap(&nums[start], &nums[end]);
        start += 1;
        end -= 1;
    }
}

void rotate(int* nums, int numsSize, int k) {
    k %= numsSize;
    reverse(nums, 0, numsSize - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, numsSize - 1);
}

3. 我再研究一下