冒泡排序,快速排序,leecode例题场景分析

Leetcode   189. 旋转数组

如果想了解 快速排序直接看方法2

给定一个数组,将数组中的元素向右移动 个位置,其中 是非负数。

冒泡排序,快速排序,leecode例题场景分析

说明:

  • 尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。
  • 要求使用空间复杂度为 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);
    }

  

 

上一篇:LeeCode_判定字符是否唯一


下一篇:blender2.7.4安装three.js插件