每日一题---OJ题: 旋转数组

片头

嗨! 小伙伴们,咱们又见面啦,今天我们一起来学习一道OJ题---旋转数组

emmm,看上去好像没有那么难,我们一起来分析分析

比如: 数组里面有7个元素,分别为 1, 2, 3, 4, 5, 6, 7 , 现在我们将数组中的元素向右轮转3个位置

第一次轮转:将最后一个元素"7"放在第一个位置,后面的元素依次往后移动,变成 7, 1, 2, 3, 4, 5, 6

第二次轮转:将最后一个元素"6"放在第一个位置,后面的元素依次往后移动,变成 6, 7, 1, 2, 3, 4, 5

第三次轮转:将最后一个元素"5"放在第一个位置,后面的元素依次往后移动,变成 5, 6, 7, 1, 2, 3, 4

针对这道题,我们提供3种思路:

思路1: 右旋k次, 每次挪动旋转一位

定义一个变量temp,用来保存最后一个元素,将最后一个元素放到第一个位置,同时将后面的元素依次往右移动

代码如下:

void Reverse(int arr[], int time, int size) {
    time = time % size; //求具体的旋转次数
    for (int i = 0; i < time; i++) {
        //将最后一个元素保存在temp变量中
        int temp = arr[size - 1];
        for (int j = size-2; j >=0 ; j--) {
        //从下标为size-2的元素开始,一直到下标为0的元素,依次往后移动一位
            arr[j + 1] = arr[j];
        }
        //将最后一个元素放入第一个位置(还原)
        arr[0] = temp;
    }
}
int main() {
    int time = 3;
    int arr[] = { 1,2,3,4,5,6,7 };
    int sz = sizeof(arr) / sizeof(arr[0]);
    Reverse(arr, time,sz);
    for (int i = 0; i < sz; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

运行结果为:

5 6 7 1 2 3 4

But,当我们把代码放到leetcode上面显示不通过

哈哈哈哈,说明这道OJ题限制了时间复杂度,我们这种思路的时间复杂度为 O(n^2) ,题目不通过

那我们就换一种思路呗!

思路2: 我们把数组分成3个部分逆置,假设数组里面有7个元素,分别为 1, 2, 3, 4, 5, 6, 7 , 现在我们将数组中的元素向右轮转3个位置

第一个部分: 前n-k个逆置,这里的 n 为 7, k 为 3,也就是前4个逆置,变成 4, 3, 2, 1, 5, 6, 7

第二个部分: 后k个逆置, 这里的 k 为 3,也就是后3个逆置, 变成 4, 3, 2, 1, 7, 6, 5

第三个部分: 整体逆置,变成了 5, 6, 7, 1, 2, 3, 4

代码如下:

void Reverse1(int arr[], int start, int end) {
    int left = start;    //将start赋给left变量
    int right = end;     //将end赋给right变量

    while (left < right) 
    {     
        //当left小于right的时候,进入循环
        //用临时变量temp实现逆置(左右元素交换)
        int temp = arr[left]; 
        arr[left] = arr[right];
        arr[right] = temp;
        left++;   //每交换完一次,left向右移动
        right--;  //每交换完一次,right向左移动,直到两个变量相遇
    }    
}

int main() {
    int time = 3;
    int arr[] = { 1,2,3,4,5,6,7 };
    int sz = sizeof(arr) / sizeof(arr[0]);

    Reverse1(arr, 0, sz - time - 1);     //前n-k个逆置
    Reverse1(arr, sz - time, sz - 1);    //后k个逆置
    Reverse1(arr, 0, sz - 1);            //整体逆置

    for (int i = 0; i < sz; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

运行结果为:

5 6 7 1 2 3 4

同时,我们将代码放到leetcode当中,显示通过

嗯,这种方法好是好,但是好像我如果第一次做这种题,肯定想不出来,那有木有第3种思路呢?

有的! 接下来我就来介绍第三种思路

思路3: 我们可以定义一个新的数组,用memcpy函数将原数组的内容拷贝到新数组中去,拷贝元素的同时,也就完成了逆置

代码如下:

void Reverse2(int arr[], int size, int time) {
    time = time % size;   //求出最终旋转次数
    int temp[20] = { 0 }; //定义一个临时数组temp,初始化数组为0

             //将原数组的后time个数拷贝到临时数组temp的前面位置中
    memcpy(temp, arr + size - time, sizeof(int) * time); 
             //将原数组的前size-time个数拷贝到临时数组temp的后面位置中  
    memcpy(temp + time, arr, sizeof(int) * (size - time)); 
            //将临时数组temp的所有元素拷贝回原数组
    memcpy(arr, temp, sizeof(int) * size);                  
}

int main() {
    int nums[] = { 1,2,3,4,5,6,7 };
    int time = 3;
    int size = sizeof(nums) / sizeof(nums[0]);
    Reverse2(nums, size, time);
    for (int i = 0; i < size; i++) {
        printf("%d ", nums[i]);
    }
    return 0;
}

运行结果为: