Leetcode 189. 旋转数组
如果想了解 快速排序直接看方法2
给定一个数组,将数组中的元素向右移动 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); }