自学内容网 自学内容网

【专项刷题】— 快排

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. 代码:
    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)!