分治

2024-10-26 07:22:32

颜色分类

在这里插入图片描述

把数组分成四段:

  1. 元素为 0
  2. 元素为 1
  3. 未划分
  4. 元素为 2

不是很难~

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    public void sortColors(int[] nums) {
        int k = nums.length - 1, i = 0, f = -1;
        while (i <= k) {
            if (nums[i] == 2) {
                swap(nums, i, k--);
            } else if (nums[i] == 0) {
                swap(nums, i++, ++f);
            } else {
                i++;
            }
        }
    }

排序数组 (快排)

在这里插入图片描述

写一个快排~
取随机数时卡了一下.

坑;

  • 快排不优化一下过不了~
private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    private int quick(int[] nums, int left, int right) {
        if (left >= right) return left;
        int partation = nums[new Random().nextInt(right - left + 1) + left];
        for (int i = left; i <= right; ) {
            if (nums[i] < partation) {
                swap(nums, i++, left++);
            } else if (nums[i] > partation) {
                swap(nums, i, right--);
            } else {
                i++;
            }
        }
        return left;
    }

    private void quickSort(int[] nums, int start, int end) {
        if (start >= end) return;
        int pos = quick(nums, start, end);
        quickSort(nums, start, pos - 1);
        quickSort(nums, pos + 1, end);
    }

    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }

题解代码更好~

class Solution {

    private void swap(int[] nums,int i,int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    private void quickSort(int[] nums,int start,int end) {
        if(start >= end) return;
        int pos = nums[new Random().nextInt(end-start+1)+start];
        int left = start - 1,right = end + 1,i = start;
        while(i < right) {
            if(nums[i] < pos) swap(nums,++left,i++);
            else if(nums[i] > pos) swap(nums,i,--right);
            else i++;
        }
        quickSort(nums,start,left);
        quickSort(nums,right,end);
    }
    public int[] sortArray(int[] nums) {
        quickSort(nums,0,nums.length-1);
        return nums;
    }
}

数组中的第K个最大元素

在这里插入图片描述

做这道题时,我因为边界问题卡了半天,后来发现自己把区间范围搞错了,浪费了10多分钟.

  • [start , left] : 小于 pos
  • [left + 1 , right - 1] : 等于 pos
  • [right , end] : 大于pos
private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    private int find(int[] nums, int k, int start, int end) {
        if (start >= end)
            return nums[start];
        int left = start - 1, i = start, right = end + 1;
        int pos = nums[new Random().nextInt(end - start + 1) + start];
        while (i < right) {
            if (nums[i] < pos)
                swap(nums, i++, ++left);
            else if (nums[i] > pos)
                swap(nums, i, --right);
            else
                i++;
        }
        if (end - right + 1 >= k) {
            return find(nums, k, right, end);
        } else if (end - left >= k) {
            return nums[right - 1];
        } else {
            return find(nums, k - (end - left), start, left);
        }
    }

    public int findKthLargest(int[] nums, int k) {
        return find(nums, k, 0, nums.length - 1);
    }

库存管理 III

在这里插入图片描述
跟上一题很像.

主要是最后的分段条件需要想想,前面的都一样~
在这里插入图片描述

class Solution {
    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    private void qsort(int[] stock, int cnt, int start, int end) {
        if (start >= end)
            return;
        int left = start - 1, i = start, right = end + 1;
        int pos = stock[new Random().nextInt(end - start + 1) + start];
        while (i < right) {
            if (stock[i] < pos)
                swap(stock, i++, ++left);
            else if (stock[i] > pos)
                swap(stock, i, --right);
            else
                i++;
        }

        if (left - start + 1 > cnt) {
            qsort(stock, cnt, start, left);
        } else if (right - start >= cnt) {
            return;
        } else {
            qsort(stock, cnt - (right - start), right, end);
        }
    }

    public int[] inventoryManagement(int[] stock, int cnt) {
        qsort(stock, cnt, 0, stock.length - 1);
        return Arrays.copyOf(stock, cnt);
    }
}

排序数组 (归并排序)

在这里插入图片描述

归并排序很简单~

  1. 把数组分成两个区间.
  2. 分别给左右两个区间排序
  3. 合并两个有序数组
  4. 把排序后的结果还原到数组中
class Solution {
    // 辅助数组
    private int[] arr;

    private void mergeSort(int[] nums, int start, int end) {
        if (start >= end)
            return;
        
        // 把数组划分成两个区间 [start,mid] [mid+1,end]
        // 把左右区间排序
        int mid = start + (end - start) / 2;
        mergeSort(nums, start, mid);
        mergeSort(nums, mid + 1, end);

        // 合并两个有序数组
        int left = start, right = mid + 1, k = 0;
        while (left <= mid && right <= end) {
            if (nums[left] < nums[right]) {
                arr[k++] = nums[left++];
            } else {
                arr[k++] = nums[right++];
            }
        }
        while (left <= mid) {
            arr[k++] = nums[left++];
        }
        while (right <= end) {
            arr[k++] = nums[right++];
        }
        int i = 0;
        while (start <= end) {
            nums[start++] = arr[i++];
        }
    }

    public int[] sortArray(int[] nums) {
        // 给辅助数组申请一块空间
        arr = new int[nums.length];
        mergeSort(nums, 0, nums.length - 1);
        return nums;
    }
}

题解代码:

class Solution {
    // 辅助数组
    private int[] arr;

    private void mergeSort(int[] nums, int start, int end) {
        if (start >= end)
            return;

        // 把数组划分成两个区间 [start,mid] [mid+1,end]
        // 把左右区间排序
        int mid = start + (end - start) / 2;
        mergeSort(nums, start, mid);
        mergeSort(nums, mid + 1, end);

        // 合并两个有序数组
        int left = start, right = mid + 1, k = 0;
        while (left <= mid && right <= end) {
            arr[k++] = nums[left] < nums[right] ? nums[left++] : nums[right++];
        }
        while (left <= mid) {
            arr[k++] = nums[left++];
        }
        while (right <= end) {
            arr[k++] = nums[right++];
        }

        // 还原
        for (int i = start; i <= end; i++)
            nums[i] = arr[i - start];
    }

    public int[] sortArray(int[] nums) {
        // 给辅助数组申请一块空间
        arr = new int[nums.length];
        mergeSort(nums, 0, nums.length - 1);
        return nums;
    }
}

交易逆序对的总数

在这里插入图片描述
十分甚至九分的不好理解.
思路很简单

  1. 把数组分成两块, [left , mid] [mid + 1 , end]
  2. 在[left , mid] 上用递归寻找有多少个逆序对 + 排序
  3. 在[mid + 1 , end] 上用递归寻找有多少个逆序对 + 排序
  4. 在[left , mid]中选择一个数, 在[mid + 1 , end]中选择一个数,寻找逆序对+排序

问题在于怎么把寻找逆序对和排序结合起来.

不太明白啥时候用升序,啥时候用降序.

  • 升: 求当前元素的前面有多少个元素比我大
  • 降: 求当前元素的后面有多少个元素比我小

在写递归的时候,你要相信这个函数能做到它该做到的功能.只管往下写.

升序版本:

class Solution {

    private int tmp[];

    public int merge(int[] arr, int start, int end) {
        int sum = 0;
        if (start >= end)
            return sum;

        int mid = start + (end - start) / 2;
		// 划分区间 [left , mid] [mid + 1 , end]
        sum += merge(arr, start, mid);
        sum += merge(arr, mid + 1, end);

		// 升序
        int left = start, right = mid + 1, k = 0;
        while (left <= mid && right <= end) {
            if (arr[left] <= arr[right]) {
                tmp[k++] = arr[left++];
            } else {
                tmp[k++] = arr[right++];
                sum += mid - left + 1;
            }
        }

		// 归并排序收尾
        while (left <= mid)
            tmp[k++] = arr[left++];

        while (right <= end)
            tmp[k++] = arr[right++];

        for (int i = start; i <= end; i++) {
            arr[i] = tmp[i - start];
        }

        return sum;
    }

    public int reversePairs(int[] record) {
        tmp = new int[record.length];
        return merge(record, 0, record.length - 1);
    }
}

降序版本:

class Solution {

    private int tmp[];

    public int merge(int[] arr, int start, int end) {
        int sum = 0;
        if (start >= end)
            return sum;
            

        int mid = start + (end - start) / 2;

        sum += merge(arr, start, mid);
        sum += merge(arr, mid + 1, end);

        int left = start, right = mid + 1, k = 0;
        while (left <= mid && right <= end) {
            if (arr[left] <= arr[right]) {
                tmp[k++] = arr[right++];
            } else {
                tmp[k++] = arr[left++];
                sum += end - right + 1;
            }
        }
        while (left <= mid)
            tmp[k++] = arr[left++];

        while (right <= end)
            tmp[k++] = arr[right++];

        for (int i = start; i <= end; i++) {
            arr[i] = tmp[i - start];
        }

        return sum;
    }

    public int reversePairs(int[] record) {
        tmp = new int[record.length];
        return merge(record, 0, record.length - 1);
    }
}

计算右侧小于当前元素的个数

在这里插入图片描述
跟上一题很像, 但是题目要求返回 List<Integer> , 在上一个题目的基础上,还需要记录下来原始数组中元素对应的下标.用一个数组index来记录就行,但是arr中的元素咋交换,index就咋交换.

我在最后的int[]转List<Integer>想了一会,能不能一行解决,没想到,不会~

坑:

  • 需要创建两个辅助数组,一个给arr用,一个给index用. 而且需要同步交换.
  • ret[index[left]] += end - right + 1; 中间是 += 而不是 = 
class Solution {
    private int[] tmpNums;
    private int[] tmpIndex;

    private void merge(int[] arr, int start, int end, int[] ret, int[] index) {
        if (start >= end)
            return;

        // 划分区间 + 排序
        int mid = start + (end - start) / 2;

        merge(arr, start, mid, ret, index);
        merge(arr, mid + 1, end, ret, index);

        // 一左一右
        int left = start, right = mid + 1, k = 0;
        while (left <= mid && right <= end) {
            if (arr[left] <= arr[right]) {
                // 同步交换
                tmpNums[k] = arr[right];
                tmpIndex[k++] = index[right++];
            } else {
                // 计入结果 + 同步交换
                ret[index[left]] += end - right + 1;

                tmpNums[k] = arr[left];
                tmpIndex[k++] = index[left++];
            }
        }

        // 归并收尾
        while (left <= mid) {
            tmpNums[k] = arr[left];
            tmpIndex[k++] = index[left++];
        }
        while (right <= end) {
            // 同步交换
            tmpNums[k] = arr[right];
            tmpIndex[k++] = index[right++];
        }
        for (int i = start; i <= end; i++) {
            arr[i] = tmpNums[i - start];
            index[i] = tmpIndex[i - start];
        }

    }

    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        List<Integer> list = new ArrayList<>();
        tmpNums = new int[n];
        tmpIndex = new int[n];

        // 记录下标
        int[] index = new int[n];

        // 初始化 index 数组
        for (int i = 0; i < n; i++) {
            index[i] = i;
        }
        int[] ret = new int[n];
        merge(nums, 0, n - 1, ret, index);
        for (int x : ret) {
            list.add(x);
        }
        return list;
    }
}

翻转对

在这里插入图片描述

把归并和求sum分开写就OK.

降序版本:

class Solution {
    int[] tmp;

    private int merge(int[] nums, int start, int end) {
        int sum = 0;
        if (start >= end)
            return sum;

        int mid = start + (end - start) / 2;
        sum += merge(nums, start, mid);
        sum += merge(nums, mid + 1, end);
		// 求sum
        int left = start, right = mid + 1, k = 0;
        while (left <= mid && right <= end) {
            if (nums[left] <= (long) 2 * nums[right]) {
                right++;
            } else {
                sum += end - right + 1;
                left++;
            }
        }
		
		// 归并
        left = start;
        right = mid + 1;
        while (left <= mid && right <= end) {
            if (nums[left] <= nums[right]) {
                tmp[k++] = nums[right++];
            } else {
                tmp[k++] = nums[left++];
            }
        }
        while (left <= mid) {
            tmp[k++] = nums[left++];
        }
        while (right <= end) {
            tmp[k++] = nums[right++];
        }

        for (int i = start; i <= end; i++) {
            nums[i] = tmp[i - start];
        }

        return sum;
    }

    public int reversePairs(int[] nums) {
        int n = nums.length;
        tmp = new int[n];
        return merge(nums, 0, n - 1);
    }
}

升序版本:

class Solution {
    int[] tmp;

    private int merge(int[] nums, int start, int end) {
        int sum = 0;
        if (start >= end)
            return sum;

        int mid = start + (end - start) / 2;
        sum += merge(nums, start, mid);
        sum += merge(nums, mid + 1, end);

        int left = start, right = mid + 1, k = 0;
        while (left <= mid && right <= end) {
            if (nums[left] <= (long) 2 * nums[right]) {
                left++;
            } else {
                sum += mid - left + 1;
                right++;
            }
        }

        left = start;
        right = mid + 1;
        while (left <= mid && right <= end) {
            if (nums[left] <= nums[right]) {
                tmp[k++] = nums[left++];
            } else {
                tmp[k++] = nums[right++];
            }
        }
        while (left <= mid) {
            tmp[k++] = nums[left++];
        }
        while (right <= end) {
            tmp[k++] = nums[right++];
        }

        for (int i = start; i <= end; i++) {
            nums[i] = tmp[i - start];
        }

        return sum;
    }

    public int reversePairs(int[] nums) {
        int n = nums.length;
        tmp = new int[n];
        return merge(nums, 0, n - 1);
    }
}
上一篇：大数据治理的挑战与实践：从数据管理到智能决策的全流程解析


下一篇：vba学习系列(8)--指定列单元格时间按时间段计数