Leetcode 189. 旋转数组
如果想了解 快速排序直接看方法2 环状跳跃直接看方法3
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
说明:
- 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
- 要求使用空间复杂度为 O(1) 的 原地 算法。
思路： 方法1.既然要求空间复杂度为O(1)，肯定是时间换空间，首先想到的是模拟操作（类似冒泡排序），跟题目解释一样的算法。时间复杂度O（k*n）n是数组长度。
class Solution {
private void swap(int[] nums,int i,int j){
int temp = nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
public void rotate(int[] nums, int k) {
int len = nums.length;
if(len<2) return;
int ys = k%len;
int temp = 0,cnt=0,i=len-1;
while(cnt!=ys){//总共需要移动k次，每次把需要移动的数字暂存起来，最后赋值
i=len-1;cnt++;
temp = nums[i];
for(int j=i;j>=1;j--)
swap(nums,j,j-1);
nums[0]=temp;//每次把最后一个值放到第一位
}
}
}
方法2 :先移动一部分数据（保证前面的数据正确），然后再快速排序。（注意：这个解法不适合leetcode，原因：题目没说原数组是有序数组····我进坑了，既然都进坑了，那么就算是经验了） 总结下快速排序（递归）：找数组第一个作为基准数据temp，两个指针left和right。步骤1：right指针找到一个小于temp，把right的值赋给left，否则就right--。步骤2：可以开始移动left指针了，如果找到一个数据比temp大，则把left的值赋给right，否则left++。步骤3：如果left<right重复步骤1和2。注意：递归的思路一定要清晰，把index作为递归的左右分界点，分别对分割后的左右两个数组进行快速排序。
private void swap(int[] nums,int i,int j){
int temp = nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
private void quickSort(int[] nums,int l,int r){
if(l<r){//注意：递归的条件必须是当前长度大于1
int index = getIndex(nums,l,r);
//index的左右都是有序数列分别对左右数列进行递归
quickSort(nums,l,index-1);
quickSort(nums,index+1,r);}
}
private int getIndex(int[] nums,int l,int r){
int left = l;
int right = r;
int temp = nums[left];//作为基础数据用作比较
while(left<right){
//当左面指针与右面指针不重合说明左右指针可以继续移动
while(left<right&&nums[right]>=temp){
right--;//右面指针所指数据大于temp基础数据，就继续左移指针
}
nums[left]=nums[right];//找到比基础数据小的数据了，替换到left
while(left<right&&nums[left]<=temp){
left++;//left指针所指数据小于基础数据，于是右移
}
nums[right]=nums[left];
}
nums[left]=temp;//此时left=right 把temp基础数据归位！
return left;
}
public void rotate(int[] nums, int k) {
int len = nums.length;
if(len<2) return;
int ys = k%len;
int temp = 0;
for(int i=0,j=len-ys;i<ys;i++,j++){
//第一步先把（1,2,3,4,5,6,7）——（5,6,7,4,1,2,3）
swap(nums,i,j);
}
//使用快速排序新的数组nums的起始点l=ys，终点r=len-1
quickSort(nums,ys,len-1);
}
方法3 （1,2,3,4,5,6,7）当k=2时，最终的结果是（6,7,1,2,3,4,5）。把数组想象成同学调座位，步骤1：2要去4的位置，那么4就要离开；步骤2： 4要去6的位置，那么6就要离开；步骤3：6要去1的位置，那么1就要离开；步骤4：1要去3的位置，3就要离开；步骤5:3要去5的位置，5就要离开；步骤6:5要去7的位置，7要离开；步骤7:7要去2的位置。结束条件，所有的7个同学都循环了一遍。
class Solution {
private int gys(int a,int b){//公约数=2就需要多循环一次=3多循环两次
return a%b==0?b:gys(b%a,a);
}
public void rotate(int[] nums, int k) {
int len = nums.length;
if(len<2) return;
if(k==0) return;
int temp = 0;
int gys = gys(k,len);//求出公约数，知道循环的次数
for(int cnt=0;cnt<gys;cnt++){
int store=nums[cnt];
for(int i=cnt;;i+=k){
if(i!=cnt&&i%len==cnt)break;
temp = nums[(i+k)%len];//把被挤走的值存放在temp里面
nums[(i+k)%len]=store;//上一次循环存储的值放进来
store = temp; // 这一轮暂存的值temp作为下一轮存储的值
}
}
}
}