排序思维衍生题目

归并merge思想

小数和

数组中的每个数，它前面比它小的数的所有和，称为数组的小数和。
举例
1，2，3，4，5

思路转换：求每个数右边大于它的数量，用数量✖️自己的数即可。
举例
1，2，3，4，5

使用归并的思想，在merge时，左右子数组比较，一旦出现左小于右时，就开始累加这个小数和。
由于参与merge的两个数组都是有序的，因此可以直接根据下标计算出右数组有几个大于当前左数的。
因此该方法是依赖归并后的有序性的，归并排序的代码一行不能少。
注意merge时如果左右有相等的，要优先排右边的数到temp数组。这样优先把右边相等的排空了才能方便根据下标算出右边有多少个元素大于左边当前元素

public class SmallSum {
    private int sum = 0;
    public static void main(String[] args) {
        SmallSum mergeSort = new SmallSum();
        int[] nums = {5,2,7,3,1,9};
        mergeSort.sort(nums);
        System.out.println();
    }
    public int[] sort(int[] nums){
        if (nums.length < 2){
            return 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) >> 1);
        sort(nums,left,mid);
        sort(nums,mid+1,right);
        merge(nums,left,mid,right);
    }
    private void merge(int[] nums, int left, int mid, int right){
        int[] temp = new int[right - left +1];
        int leftStart = left, rightStart = mid+1 , index = 0;
        while (leftStart <= mid && rightStart <= right){
            if (nums[leftStart] < nums[rightStart]){
                temp[index++] = nums[leftStart];
                // 小数和的代码就这一行，其他都是原汁原味的归并排序
                sum = sum + nums[leftStart] * (right - rightStart + 1);
                leftStart++;
            }else {
                temp[index++] = nums[rightStart];
                rightStart++;
            }
        }
        while (leftStart <= mid){
            temp[index++] = nums[leftStart++];
        }
        while (rightStart <= right){
            temp[index++] = nums[rightStart++];
        }
        index = 0;
        while (left <= right){
            nums[left++] = temp[index++];
        }
    }
}

逆序对

数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。

和上面小数和思路一样，小数和是求右边大于它的数量，这个是求右边小于它的数量
下面的代码set的意义在于保留了所有逆序对，可以进行打印，leetcode中的题只求数量要改成count计数，使用set存储会超时。

        Set<int[]> sets = new HashSet<>();
    public int reversePairs(int[] nums) {
        sort(nums,0,nums.length-1);
        return sets.size();
    }
    private void sort(int[] nums, int left, int right){
        if (left >= right){
            return;
        }
        int mid = left + ((right - left) >> 1);
        sort(nums,left,mid);
        sort(nums,mid+1,right);
        merge(nums,left,mid,right);
    }
    private void merge(int[] nums, int left, int mid, int right){
        int temp[] = new int[right - left + 1];
        int leftIndex = left, rightIndex = mid+1, index = 0;
        while (leftIndex <= mid && rightIndex <= right){
            // 相等的不做逆序记录
            if (nums[leftIndex] <= nums[rightIndex]){
                temp[index++] = nums[leftIndex++];
            }else {
                // 如果左边比右边大，则左边剩余所有的都比当前右边的大
                for (int i = leftIndex; i <= mid; i++) {
                    sets.add(new int[]{nums[i],nums[rightIndex]});
                }
                temp[index++] = nums[rightIndex++];
            }
        }
        while (leftIndex <= mid){
            temp[index++] = nums[leftIndex++];
        }
        while (rightIndex <= right){
            temp[index++] = nums[rightIndex++];
        }
        index = 0;
        while (left <= right){
            nums[left++] = temp[index++];
        }
    }

快排partition思想

荷兰国旗问题

给定数组和target，将数组小于target的放左边，等于target的放中间，大于target的放右边。

/**
 * 给定一个target，小于target的放左边，等于target的放中间，大于target的放右边
 */
public class Helan {
    public static void main(String[] args) {
        Helan helan = new Helan();
        int[] nums = {4,1,6,2,8,5,0,5,5};
        helan.execute(nums,5);
        System.out.println();
    }
    /**
     * 维护左右指针，分别代表小于和大于target的区域
     * index指针从左到右，小于target就和left的交互，大于就和right交换，等于的直接下一个
     * 注意循环条件要覆盖到index = right，因为left和right指向的位置都是下一个要替换的位置
     * right指向的位置还没被index访问到
     */
    public void execute(int[] nums, int target){
        int left = 0 , right = nums.length-1;
        int index = 0;
        while (index <= right){
            if (nums[index] < target){
                swap(nums,left++,index);
            }else if (nums[index] > target){
                swap(nums,right--,index);
            }
            index++;
        }
    }
    private void swap(int[] nums, int i, int j){
        if (i == j) {
            return;
        }
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

堆排序扩展

一个近似有序的数组，每个元素距离它正确的有序位置距离不超过k,选择一个排序算法对它排序。
使用最小堆实现，我们将前k+1个数放入最小堆中，则此时数组中的最小值肯定是最小堆的堆顶。
因为k的约束，最小值肯定是在数组的前k+1个数中的，以此类推，逐个弹出堆顶，压入后面的元素

/**
 * @author jiangwenbin
 * @date 2021/12/23
 *
 * 一个近似有序的数组，每个元素距离它正确的有序位置距离不超过k
 * 选择一个排序算法对它排序。
 *
 * 使用最小堆实现，我们将前k+1个数放入最小堆中，则此时数组中的最小值肯定是最小堆的堆顶。
 * 因为k的约束，最小值肯定是在数组的前k+1个数中的，以此类推，逐个弹出堆顶，压入后面的元素
 */
public class KDistanceSort {
    public static void main(String[] args) {
        KDistanceSort kDistanceSort = new KDistanceSort();
        int[] nums = {1,3,2,5,4,6};
        kDistanceSort.sort(nums,3);
        System.out.println();
    }
    public void sort(int[] nums, int k){
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int i = 0;
        for (int length = Math.min(nums.length,k+1); i < length; i++) {
            heap.add(nums[i]);
        }
        int index = 0;
        for (; i < nums.length; i++) {
            nums[index++] = heap.remove();
            heap.add(nums[i]);
        }
        while (!heap.isEmpty()){
            nums[index++] = heap.remove();
        }
    }
}