【专项刷题】— 快排

1、颜色分类 - 力扣（LeetCode）

思路：

1. 创建三个指针，然后把数组分为三个区域
2. 遍历
3. 代码：

   class Solution {
       public void swap(int[] nums, int i, int j){
           int t = nums[i];
           nums[i] = nums[j];
           nums[j] = t;
       }
       public void sortColors(int[] nums) {
           int left = -1;
           int right = nums.length;
           int i = 0;
           while(i < right){
               if(nums[i] == 0){
                   swap(nums, ++left, i++);
               }else if(nums[i] == 1){
                   i++;
               }else{
                   swap(nums, --right, i);
               }
           }
       }
   }

2、 排序数组 - 力扣（LeetCode）

思路：

1. 题1的解法，只需优化一下，随机生成被比较的值即可
2. 代码：

   class Solution {
       public int[] sortArray(int[] nums) {
           qsort(nums, 0, nums.length - 1);
           return nums;
       }
       public void qsort(int[] nums, int l, int r){
           if(l >= r){
               return;
           }
           //随机生成值
           int key = nums[(new Random().nextInt(r - l + 1) + l)];
           int left = l-1;
           int i = l;
           int right = r+1;
           while(i < right){
               if(nums[i] < key){
                   swap(nums,++left,i++);
               }else if (nums[i] == key){
                   i++;
               }else{
                   swap(nums, --right, i);
               }
           }
           qsort(nums, l, left);
           qsort(nums, right, r);
       }
       public void swap(int[] nums, int l,int r){
           int tmp = nums[l];
           nums[l] = nums[r];
           nums[r] = tmp;
       }
   }

 3、数组中的第K个最大元素 - 力扣（LeetCode）

思路：

1. 在快排的基础上寻找这个第k大的数
2. 把每个区间的元素的个数标出来，然后：
3. 代码：

   class Solution {
       public int findKthLargest(int[] nums, int k) {
           return qsort(nums, 0, nums.length - 1, k);
       }
       public int qsort(int[] nums, int l, int r, int k){
   
           if(l == r){
               return nums[l];
           }
   
           //选择一个基准
           int key = nums[new Random().nextInt(r-l+1)+l];
           //根据基准将数组分为三个部分
           int left = l - 1;
           int right = r + 1;
           int i = l;
           while(i < right){
               if(nums[i] < key){
                   swap(nums, ++left, i++);
               }else if(nums[i] == key){
                   i++;
               }else{
                   swap(nums, --right, i);
               }
           }
           //分类讨论a:[l,left] b:[left+1,right-1] c:[right,r]
           int b = right - left - 1;
           int c = r - right + 1;
           if(c >= k){
               return qsort(nums,right,r,k);
           }else if(b+c >= k){
               return key;
           }else{
               return qsort(nums, l, left, k - b- c);
           }
       }
       public void swap(int[] nums, int l, int r){
           int tmp = nums[l];
           nums[l] = nums[r];
           nums[r] = tmp;
       }
   }

4、最小K个数 - 力扣（LeetCode） 

思路：

1. 与上一题的思路一样只不过是在分类讨论的时候改变一下
2. 
3. 代码：

   class Solution {
       public int[] smallestK(int[] nums, int k) {
           qsort(nums, 0, nums.length - 1, k);
           int[] ret = new int[k];
           for(int i = 0; i < k; i++){
               ret[i] = nums[i];
           }
           return ret;
       }
   
       public void qsort(int[] nums, int l, int r, int k){
           if(l >= r){
               return;
           }
           //随机生成基准
           int key = nums[new Random().nextInt(r-l+1)+l];
           //
           int left = l-1;
           int right = r+1;
           int i = l;
           while(i < right){
               if(nums[i] < key){
                   swap(nums, ++left, i++);
               }else if(nums[i] == key){
                   i++;
               }else{
                   swap(nums, --right, i);
               }
           }
           //分类讨论
           int a = left - l +1;
           int b = right - left - 1;
           if(a > k){
               qsort(nums, l, left, k);
           }else if(a+b > k){
               return;
           }else{
               qsort(nums, right, r, k-a-b);
           }
       }
   
       public void swap(int[] nums, int l, int r){
           int tmp = nums[l];
           nums[l] = nums[r];
           nums[r] = tmp;
       }
   }

原文地址：https://blog.csdn.net/weixin_62678196/article/details/140559704

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！