leetcode - 分治思想

分治 - 快排

这里快排我们统一使用 数组分三块 和 随机产生基准值的方法实现排序

数组分三块:

. - 力扣（LeetCode）

整个思想即将数组按照基准值分为三个区间 , 具体实现: 三指针实现.  遍历指针 , 左区间右边界指针 , 右区间左边界指针

class Solution {
    //三指针法
    //格外注意边界值问题
    //[0,left - 1]  值为0
    //[left,right]  值为1
    //[right + 1,nums,length - 1] 值为2
    public void sortColors(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        int i = 0;
        while(i <= right) {
            if(nums[i] == 0) swap(left ++,i ++,nums);
            else if(nums[i] == 1) i ++;
            else swap(right --,i,nums);//注意这里右边交换时i不用++，
        }
    }
    private void swap(int left,int right,int[] nums) {
        int cur = nums[left];
        nums[left] = nums[right];
        nums[right] = cur;
    }
}

过程

为什么要使用随机数?   基于随机数产生基准值而进行快排时,时间复杂度最为接近O(Logn)

class Solution {
    public int[] sortArray(int[] nums) {
        sort(0 , nums.length - 1 , nums);
        return nums;
    }
    private void sort(int left , int right , int[] nums){
        //递归结束条件
        if(left >= right) return;

        int random = new Random().nextInt(right - left + 1);
        int flag = nums[random + left];//确定基准值
        int leftFlag = left;
        int rightFlag = right;
        int cur = left;
        while(cur <= rightFlag){
            if(nums[cur] == flag) cur ++;
            else if(nums[cur] > flag) swap(nums , cur , rightFlag --);
            else swap(nums , cur++ , leftFlag ++);
        }//循环结束时,leftModel - 1为左区间最后一个元素 , leftModel + 1为右区间最后一个元素

        //递归
        sort(left , leftFlag - 1 ,nums);
        sort(rightFlag + 1 , right , nums);

    }
    private void swap(int[] nums , int l1 , int l2) {
        int cur = nums[l1];
        nums[l1] = nums[l2];
        nums[l2] = cur;
    }
 }

快速选择算法:

. - 力扣（LeetCode）    数组中第k个最大元素  , 要求时间复杂度O(n). 

这道题比较容易想到的解法是 借助堆.    但是题目中要求时间复杂度为On , 堆就不满足要求了.

时间复杂度为O(n). 我们就要想到快速选择排算法

原理:  快排数组分三段的基础上不去对每一段进行排序,而是通过三个区间的元素数量判断目标元素在哪一个区间进行分类讨论:

class Solution {
    //快速选择算法
    //基于快排数组分三块的思想:分三块后通过分类确定目标范围
    private static int dest;
    public int findKthLargest(int[] nums, int k) {
        Solution s = new Solution();
        s.quickChoose(0 , nums.length - 1 , nums , k);
        return dest;
    }
    private void quickChoose(int left , int right , int[] nums , int k){
        if(right <= left) {
            dest = nums[left];//这里不要忘记赋值
            return;
        }
        
        int flag = nums[new Random().nextInt(right - left + 1) + left];
        System.out.println(left+":" + right+":" +flag);
        int l = left;
        int r = right;
        int cur = left;
        while(cur <=  r){
            if(nums[cur] == flag) cur ++;
            else if(nums[cur] > flag) swap(nums , r -- , cur);//注意右边换过来的是一个新值,cur不进行++
            else if(nums[cur] < flag) swap(nums , l ++ , cur ++);
        }
        //分类讨论 , 根据区间内元素的数量确定下一步计划
        //1: 目标元素在大于基准值的区间
        if(right - r >= k) quickChoose(r + 1 , right ,nums , k);
        //2: 目标元素等于基准值,直接进行返回
        else if(right - l + 1 >= k) {
            dest = flag;
            return;
        }
        //3:目标元素在小于基准值的区间
        else quickChoose(left , l - 1, nums , k - (right - l + 1));
    }
    private void swap(int[] nums , int num1 , int num2) {
        int cur = nums[num1];
        nums[num1] = nums[num2];
        nums[num2] = cur;
    }
 }

. - 力扣（LeetCode）   库存管理: 选出库存最小的cnt个商品

class Solution {
    private int str;
    private int end;
    //使用快速选择排序
    public int[] inventoryManagement(int[] stock, int cnt) {
        quickSort(stock , 0 , stock.length - 1 , cnt);
        int[] dest = new int[cnt];
        for(int i = 0;i < cnt;i ++) {
            dest[i] = stock[i];
        }
        return dest;
    }
    private void quickSort(int[] nums , int left , int right , int cnt) {
        if(left >= right) return;
        int l = left;
        int r = right;
        int cur =  left;
        int flag = nums[new Random().nextInt(right - left + 1) + left];
        while(cur <= r){
            if(nums[cur] == flag) cur ++;
            else if(nums[cur] > flag) swap(r -- , cur , nums);
            else swap(l ++ , cur++ , nums);
        }
        //分类讨论
        if(l - left > cnt) quickSort(nums , left , l - 1 , cnt);
        else if(r - left + 1 >= cnt) return;
        else quickSort(nums , r + 1, right , cnt - (r - left + 1));
    }
    private void swap(int num1 , int num2 , int[] nums) {
        int temp = nums[num1];
        nums[num1] = nums[num2];
        nums[num2] = temp;
    }
}

分治 - 归并

核心思想:   将一个问题分成若干个规模较小的子问题，分别求解后，再将子问题的结果合并，得到原问题的解。归并排序的核心步骤分为两个部分：“分”和“合”。

归并排序

:. - 力扣（LeetCode）

 public int[] sortArray(int[] nums) {
        sort(nums , 0 , nums.length - 1);
        return nums;
    }
    private void sort(int[] nums , int left , int right) {
        if(left >= right) return;
        //不断递归,将数组分割成俩部分,对两部分别再进行分割,直到每一部只剩下一个元素 , 俩俩进行合并
        int mid = left + (right - left) / 2;
        sort(nums , left , mid);
        sort(nums , mid + 1 , right);

        sortHelper(nums , left , mid , right);//合并的逻辑
    }
    //合并的俩个数组分别已经有序 , 建立一个新数组,设置俩个指针对俩个数组进行比较赋值到新数组上,使新数组比较
    //不要直接再原数组上进行比较交换 , 会打乱数组的有序性 , 将问题复杂化
    private void sortHelper(int[] nums , int left , int mid , int right) {
        int l = left;
        int r = mid + 1;
        int[] temp = new int[right - left + 1];
        int cur = 0;
        while(l <= mid && r <= right) {
            while(l <= mid && nums[l] <= nums[r]) temp[cur ++] = nums[l ++];
            while(r <= right && nums[r] <= nums[l]) temp[cur ++] = nums[r ++];
        }
        if(l <= mid){
            while(l <= mid)temp[cur ++] = nums[l ++];
        }
        if(r <= right) {
            while(r <= right) temp[cur ++] = nums[r ++];
        }
        for(int i = 0;i < temp.length;i ++) {
            nums[left + i] = temp[i];
        }
    }

优化 : 在进行合并时创建一个全局的,与原数组等大小的临时数组 , 这样就能避免每次进行合并时创建数组的开销.

例题

统计逆序对:  . - 力扣（LeetCode）

在上述归并的逻辑上加上 数组间统计逆序对 的逻辑即可

class Solution {
    //在进行数组之间合并排序之前加上一个统计数组间逆序队的逻辑`即可
    public int reversePairs(int[] record) {
        return sort(record , 0 , record.length - 1);
    }
    private int sort(int[] nums  , int left , int right) {
        if(left >= right) return 0;
        int mid = left + (right - left) / 2;
        int num1 = sort(nums , left , mid);
        int num2 = sort(nums , mid + 1 , right);
        int num3 = sortHelper(nums , left , mid , right);
        return (num1 + num2 + num3);
    }
    private int sortHelper(int[] nums ,int left ,int mid , int right){
        int l = left;
        int r = mid + 1;
        int count = 0;
        int[] model = new int[right - left + 1];
        int cur = 0;
        while(l <= mid && r <= right){
            while(l <= mid && nums[l] <= nums[r]) model[cur ++] = nums[l ++];
            while(r <= right && nums[r] < nums[l]){
                count += mid - l + 1;//统计逆序对; 因为合并的俩个数组已经分别有序,所以只需要统计数组间即可
                model[cur ++] = nums[r ++];
            }
        }
        while(l <= mid) model[cur ++] = nums[l ++];
        while(r <= right) model[cur ++] = nums[r ++];
        for(int i = 0;i < model.length;i ++) {
            nums[left + i] = model[i];
        }
        return count;
    }
}

右侧小于自己的数:. - 力扣（LeetCode）

首先:这道题使用暴力求解一定会超时

这道题进行归并的问题是: 归并排序后会进行元素交换, 交换后元素顺序被打乱  , 我们在进行合并数组时统计出来右侧小于当前元素的数后不知道这个元素的原始下标 .  所以这道题相比于上面求逆序对 , 需要多维护一个存储元素下标的数组.  原数组元素顺序改变时 , 这个存储下标的数组也随之进行改变 , 这样,我们就能通过nums中元素的下标拿到当前元素的初始位置 .

class Solution {
    private int[] indexMoel;//存储每个元素的原始位置 , 随着nums元素交换而交换,nums元素下标对应到indexModel上就是初始元素的位置,通过初始元素位置在dest上进行数量更新
    private int[] dest;//存储目标元素
    private int[] numsTemp;//使用全局数组进行合并,避免每次合并创建临时数组的开销
    private int[] indexTemp;
    public List<Integer> countSmaller(int[] nums) {
        indexMoel = new int[nums.length];
        numsTemp = new int[nums.length];
        indexTemp = new int[nums.length];
        dest = new int[nums.length];
        for(int i = 0;i < nums.length;i ++) {
            indexMoel[i] = i;
        }
        sort(nums , 0 , nums.length - 1);
        List<Integer> list = new ArrayList<>();
        for(int i = 0;i < dest.length;i ++) {
            list.add(dest[i]);
        }
        return list;
    }
    private void sort(int[] nums , int left , int right) {
        if(left >= right) return;
        int mid = left + (right - left) / 2;
        sort(nums , left , mid);
        sort(nums , mid + 1 , right);
        sortHelper(nums , left , mid , right);
    }
    private void sortHelper(int[] nums , int left , int mid , int right) {
        int l = left;
        int r = mid + 1;
        int cur1 = 0;
        int cur2 = 0;
        //降序排序 , 更好统计
        while(l <= mid && r <= right) {
            if(nums[l] > nums[r]) {
                dest[indexMoel[l]] += right - r + 1;//通过indexmodel拿到当前元素的初始位置进行统计
                numsTemp[cur1 ++] = nums[l];
                indexTemp[cur2 ++] = indexMoel[l ++];//indexModel随着nums的交换而交换
            }
            else {
                numsTemp[cur1 ++] = nums[r];
                indexTemp[cur2 ++] = indexMoel[r ++];
            }
        }
        while(l <= mid){
            numsTemp[cur1 ++] = nums[l];
            indexTemp[cur2 ++] = indexMoel[l ++];
        }
        while(r <= right){
            numsTemp[cur1 ++] = nums[r];
            indexTemp[cur2 ++] = indexMoel[r ++];
        }
        for(int i = 0;i < cur1;i ++) {
            nums[i + left] = numsTemp[i];
            indexMoel[i + left] = indexTemp[i]; 
        }
    }
}