力扣labuladong一刷day33天归并排序处理类似问题

力扣labuladong一刷day33天归并排序处理类似问题

归并排序模板

class Merge{

    int[] temp;

    void sort(int[] nums) {
        temp = new int[nums.length];
        sort(nums, 0, nums.length-1);
    }

    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);
        merge(nums, left, mid, right);
    }

    void merge(int[] nums, int left, int mid, int right) {
        for (int i = left; i <= right; i++) {
            temp[i] = nums[i];
        }
        int i = left, j = mid+1;
        for (int k = left; k <= right; k++) {
            if (i > mid) {
                nums[k] = temp[j++];
            } else if (j > right) {
                nums[k] = temp[i++];
            } else if (temp[i] < temp[j]) {
                nums[k] = temp[i++];
            }else {
                nums[k] = temp[j++];
            }
        }
    }
}

一、912. 排序数组

题目链接：https://leetcode.cn/problems/sort-an-array/
思路：

class Solution {
   public int[] sortArray(int[] nums) {
        Merge merge = new Merge();
        merge.sort(nums);
        return nums;
    }
}
class Merge {

    int[] temp;

    void sort(int[] nums) {
        temp = new int[nums.length];
        sort(nums, 0, nums.length-1);
    }

    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);
        merge(nums, left, mid, right);
    }

    void merge(int[] nums, int left, int mid, int right) {
        for (int i = left; i <= right; i++) {
            temp[i] = nums[i];
        }
        int i = left, j = mid+1;
        for (int k = left; k <= right; k++) {
            if (i > mid) {
                nums[k] = temp[j++];
            } else if (j > right) {
                nums[k] = temp[i++];
            } else if (temp[i] < temp[j]) {
                nums[k] = temp[i++];
            }else {
                nums[k] = temp[j++];
            }
        }
    }
}

二、315. 计算右侧小于当前元素的个数

题目链接：https://leetcode.cn/problems/count-of-smaller-numbers-after-self/
思路：采用归并排序是可以知道一个元素后面有多少元素是比它小的，这里采用一个辅助数组，记录原数组的值和索引，方便根据索引给count[]数组赋值，用归并来统计右侧小于当前位置元素主要体现在两个地方，归并排序每次划分左右两个区间，如果右区间到头了，count[i]= j-mid-1。说明比nums[i]小的元素有整个右区间这么多，这是因为右区间能抵达结尾是因为nums[i]太大，一直是右区间赋值，故是如此。另一种就是每次nums[i]<nums[j]时，count[i] = j-mid-1，这是因为当nums[i]>nums[j]时，j一直++，mid往右都是小于nums[i]的，直到nums[i]<nums[j]了，比nums[i]小的元素个数就是j-mid-1.上面说的那种情况就是第二种到达了最后一个位置的延续，这两种情况就是一种。此外计算不会重复，因为每次都是计算右侧区间的，从小往大合并，每次合并完，右侧区间都和到了左侧区间，然后再统计的话，是统计的新的右侧区间。

class Solution {
   class Pair{
        int v;
        int i;

        public Pair(int v, int i) {
            this.v = v;
            this.i = i;
        }
    }
    Pair[] temp;
    int[] count;
    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        count = new int[n];
        temp = new Pair[n];
        Pair[] arr = new Pair[n];
        for (int i = 0; i < nums.length; i++) {
            arr[i] = new Pair(nums[i], i);
        }
        sort(arr, 0, n-1);
        List<Integer> list = new ArrayList<>();
        for (int i : count) {
            list.add(i);
        }
        return list;
    }


    void sort(Pair[] arr, int left, int right) {
        if (left == right) return;
        int mid = left + (right - left) / 2;
        sort(arr, left, mid);
        sort(arr, mid+1, right);
        merge(arr, left, mid, right);
    }

    void merge(Pair[] arr, int left, int mid, int right) {
        for (int i = left; i <= right; i++) {
            temp[i] = arr[i];
        }
        int i = left, j = mid+1;
        for (int k = left; k <= right; k++) {
            if (i == mid + 1) {
                arr[k] = temp[j++];
            } else if (j == right + 1) {
                arr[k] = temp[i++];
                count[arr[k].i] += j - mid -1;
            } else if (temp[i].v > temp[j].v) {
                arr[k] = temp[j++];
            }else {
                arr[k] = temp[i++];
                count[arr[k].i] += j - mid - 1;
            }
        }
    }
}

三、493. 翻转对

题目链接：https://leetcode.cn/problems/reverse-pairs/
思路：本题要求的是nums[i] > 2 * nums[j]的数量，这个和上一题非常类似，只不过只要求数量，并不要求具体是哪个数满足条件，那么我们就可以利用归并排序的特性，在每次合并左右区间的时候，来统计左区间里有多少个满足这个条件的，另外利用左右区间都是有序这个特性，统计起来可以节省一些时间，因为是有序的，nums[i+1]只需要在nums[i]的基础上继续统计就可以。

class Solution {
    int count = 0;
    int[] temp;
    public int reversePairs(int[] nums) {
        temp = new int[nums.length];
        sort(nums, 0, nums.length-1);
        return count;
    }

    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);
        merge(nums, left, mid, right);
    }

    void merge(int[] nums, int left, int mid, int right) {
        for (int i = left; i <= right; i++) {
            temp[i] = nums[i];
        }
        int end = mid+1;
        for (int i = left; i <= mid; i++) {
            while (end <= right && (long)nums[i] > (long) nums[end] * 2) end++;
            count += end - mid - 1;
        }
        int i = left, j = mid+1;
        for (int k = left; k <= right; k++) {
            if (i > mid) {
                nums[k] = temp[j++];
            } else if (j > right) {
                nums[k] = temp[i++];
            } else if (temp[i] < temp[j]) {
                nums[k] = temp[i++];
            }else {
                nums[k] = temp[j++];
            }
        }
    }
}

四、327. 区间和的个数

题目链接：https://leetcode.cn/problems/count-of-range-sum/
思路：本题要求计算区间和的个数，即有多少个区间的和在[low, up]范围内，无非就是进行遍历，这里既然提到了区间和，我们可以使用前缀和，前缀和数组preSum，preSum[j]-preSum[i]就等于区间nums[i, j]的和，故我们可以构造前缀和数组，然后使用归并排序来遍历，每次都使用右边的区间来减左边的区间得到区间和，然后判断是否在[low, up]范围内，在的话就统计下来。

class Solution {
    long[] temp;
    int count;
    int lower, upper;
    public int countRangeSum(int[] nums, int lower, int upper) {
        int n = nums.length;
        this.lower = lower;
        this.upper = upper;
        long[] preSum = new long[n+1];
        temp = new long[n+1];
        for (int i = 0; i < n; i++) {
            preSum[i+1] = (long) nums[i] + preSum[i];
        }
        sort(preSum, 0, n);
        return count;
    }
    
    void sort(long[] nums, int left, int right) {
        if (left == right) return;
        int mid = left + (right - left) / 2;
        sort(nums, left, mid);
        sort(nums, mid+1, right);
        merge(nums, left, mid, right);
    } 
    
    void merge(long[] nums, int left, int mid, int right) {
        for (int i = left; i <= right; i++) {
            temp[i] = nums[i];
        }
        int start = mid + 1, end = mid + 1;
        for (int i = left; i <= mid; i++) {
            while (start <= right && nums[start] - nums[i] < lower) start++;
            while (end <= right && nums[end] - nums[i] <= upper) end++;
            count += end - start;
        }
        int i = left, j = mid+1;
        for (int k = left; k <= right; k++) {
            if (i > mid) {
                nums[k] = temp[j++];
            } else if (j > right) {
                nums[k] = temp[i++];
            } else if (temp[i] < temp[j]) {
                nums[k] = temp[i++];
            }else {
                nums[k] = temp[j++];
            }
        }
    }
}