数组循环移位（双指针+分治）

一时失言乱红尘 2023-01-14 12:58 92阅读 0赞

题目描述  
把一个含有N个元素的数组循环右移K位，要求算法时间复杂度为O(n)，且只允许使用两个附加变量。

题解  
分析：这道题目最容易想到的思路就是每次将数组中的元素右移一位，循环K次。先把这种思路实现下再接着分析：

void rightShift(int* arr, int N, int k)
    { 
    	 int k = k % N; //循环移动N位又回到的初始状态
         while(k--)
         { 
              int t = arr[N-1];
              for(int i = N-1; i > 0; i--)
              { 
                   arr[i] = arr[i-1];
              }
              arr[0] = t;
         }
    }

但是很明显此时时间复杂度为O(kN),不符合题目条件。

其实这里可以借鉴分治的思想，循环移位的本质规律：右移K位的过程就是把数组的两部分交换一下。  
例如：12345678，循环右移3位，实际上首先令前5位反转54321，然后令最后三位反转876，此时数组变为54321876，整体再反转一下，就变为了67812345，即循环右移3位。

//此处的反转，其实直接通过双指针，交换左指针与右指针的元素就可以了。
    void reverseArr(int* arr, int left, int right)
    { 
         while(left < right)
         { 
              int temp = arr[left];
              arr[left] = arr[right];
              arr[right] = temp;
              left++;
              right--;
         }
    }
    //分治循环移位
    void rightShift2(int* arr, int N, int k)
    { 
         k = k % N;
         reverseArr(arr, 0, N-1-k);
         reverseArr(arr, N-k, N-1);
         reverseArr(arr, 0, N-1);
    }

此时的时间复杂度就变为O(2N)了，此时满足条件。

--------------------

扩展问题：如果是循环左移呢？其实有了上面的理解，只需要修改下反转的元素就可以了，对前k个元素反转，再反转剩余的元素，最后再反转整个数组。

void leftShift(int* arr, int N, int k)
    { 
         k = k % N;
         reverseArr(arr, 0, k-1);
         reverseArr(arr, k, N-1);
         reverseArr(arr, 0, N-1);
    }

完整的本地测试代码：

#include<stdio.h>
    void rightShift(int* arr, int N, int k)
    { 
         while(k--)
         { 
              int t = arr[N-1];
              for(int i = N-1; i > 0; i--)
              { 
                   arr[i] = arr[i-1];
              }
              arr[0] = t;
         }
    
    }
    void reverseArr(int* arr, int left, int right)
    { 
         while(left < right)
         { 
              int temp = arr[left];
              arr[left] = arr[right];
              arr[right] = temp;
              left++;
              right--;
         }
    }
    void rightShift2(int* arr, int N, int k)
    { 
         k = k % N;
         reverseArr(arr, 0, N-1-k);
         reverseArr(arr, N-k, N-1);
         reverseArr(arr, 0, N-1);
    }
    void leftShift(int* arr, int N, int k)
    { 
         k = k % N;
         reverseArr(arr, 0, k-1);
         reverseArr(arr, k, N-1);
         reverseArr(arr, 0, N-1);
    }
    
    int main()
    { 
         int a[8] = { 1, 2, 3, 4, 5, 6, 7, 8};
         int N = 8;
         int k = 3;
         leftShift(a, N, k);
         for(int i=0; i < N; i++)
         { 
              printf("%d ", a[i]);
         }
    }