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

2023-12-13 05:12:12

力扣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++];
            }
        }
    }
}

文章来源:https://blog.csdn.net/qq_43511039/article/details/134893903
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。