partition-合集

字数统计: 3.9k字   |   阅读时长≈ 16分钟

partition-合集

前言

mark

1. 什么是 partition ？

我们在学习 快速排序 的时候知道，可以选择一个标定元素（称为 pivot ，一般而言随机选择），然后通过一次扫描，把数组分成三个部分：

  • 第 1 部分严格小于 pivot 元素的值；
  • 第 2 部分恰好等于 pivot 元素的值；
  • 第 3 部分严格大于 pivot 元素的值。
  • 第 2 部分元素就是排好序以后它们应该在的位置，接下来只需要递归处理第 1 部分和第 3 部分的元素。

经过一次扫描把整个数组分成 3 个部分，正好符合当前问题的场景。写对这道题的方法是：把循环不变量的定义作为注释写出来，然后再编码。

2. Leetcode-75. 颜色分类 （荷兰旗问题）

题目描述

  • 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
  • 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意:
不能使用代码库中的排序函数来解决这道题。

1
2
3
4
示例:

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

进阶：

一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗？

2.1 循环不变量

循环不变量：声明的变量在遍历的过程中需要保持定义不变。

2.2 循环不变量的设计原则

  • 说明：设计循环不变量的原则是 不重不漏。

本题的分界线定义（变量定义）

  • len 是数组的长度；
  • 变量 zero 是前两个子区间的分界点，一个是闭区间，另一个就必须是开区间；
  • 变量 i 是循环变量，一般设置为开区间，表示 i 之前的元素是遍历过的；
  • two 是另一个分界线，我设计成闭区间。

循环不变量定义如下：

  • 所有在子区间 [0, zero) 的元素都等于 0；
  • 所有在子区间 [zero, i) 的元素都等于 1；
  • 所有在子区间 [two, len - 1] 的元素都等于 2。

于是编码要解决以下三个问题：

  • 变量初始化应该如何定义；
  • 在遍历的时候，是先加减还是先交换；
  • 什么时候循环终止。

处理这三个问题，完全看循环不变量的定义。

  • 编码的时候，**zero 和 two 初始化的值就应该保证上面的三个子区间全为空；**
  • 在遍历的过程中，「下标先加减再交换」、还是「先交换再加减」就看初始化的时候变量在哪里；
  • 退出循环的条件也看上面定义的循环不变量，在i == two 成立的时候，上面的三个子区间就正好 不重不漏 地覆盖了整个数组，并且给出的性质成立，题目的任务也就完成了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
    public void sortColors(int[] nums) {
        int len = nums.length;
        if(len < 2){
            return;
        }

        // all in [0, zero) = 0
        // all in [zero, i) = 1
        // all in [two, len - 1] = 2

        // 循环终止的条件的 i == two 那么循环可以继续等待的条件是 i < two
        // 为了保证初始化的时候[0,zero) 为空  , 设置 zero = 0；
        // 所以下面遍历到 0 的时候，先交换，再加
        int zero = 0;

        // 为了保证初始化的时候[two, len - 1] 为空 设置 two = len
        // 所以下面遍历到2的时候，先减 在交换
        int two = len;
        int i = 0;

        // 当 i == two 上面的三个子区间正好覆盖了全部数组
        // 因为 循环可以继续的条件是 i  < two

        while(i < two){
            if(nums[i] == 0){
                swap(nums,i,zero);
                zero++;
                i++;
            }else if(nums[i] == 1){
                i++;
            }else{
                two--;
                swap(nums,i,two);
            }
        }
    }

    private void swap(int[] nums,int index1,int index2){
        if(index1 == index2){
            return;
        }
        nums[index1] = nums[index1] ^ nums[index2];
        nums[index2] = nums[index1] ^ nums[index2];
        nums[index1] = nums[index1] ^ nums[index2];
    }
}

复杂度分析：

  • 时间复杂度：O(N)，这里 N是输入数组的长度；
  • 空间复杂度：O(N)。

这种做法是在 Java 的 JDK 的源码中 Arrays.sort() 中学到的。

mark

3. 复习 partition习题

3.1 「力扣」第 215 题：数组中的第 K 个最大元素（中等）

题目描述

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

1
2
3
4
5
6
7
8
示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

mark

解法一 ： 优先队列

  • 这是直接明了的方法 使用 最小堆去做
  • 虽然与本系列无关，但仍然是最快捷简单的方法

思路分析 [参考链接][https://leetcode-cn.com/problems/kth-largest-element-in-an-array/solution/partitionfen-er-zhi-zhi-you-xian-dui-lie-java-dai-/]

  • 优先队列的思路是很朴素的。因为第 K 大元素，其实就是整个数组排序以后后半部分最小的那个元素。因此，我们可以维护一个有 K 个元素的最小堆：

    1、如果当前堆不满，直接添加；

    2、堆满的时候，如果新读到的数小于等于堆顶，肯定不是我们要找的元素，只有新都到的数大于堆顶的时候，才将堆顶拿出，然后放入新读到的数，进而让堆自己去调整内部结构。

  • 说明：这里最合适的操作其实是 replace，即直接把新读进来的元素放在堆顶，然后执行下沉（siftDown）操作。Java 当中的 PriorityQueue 没有提供这个操作，只好先 poll()再 offer()。

  • 思路1：把 len个元素都放入一个最小堆中，然后再 pop()出 len - k 个元素，此时最小堆只剩下 k 个元素，堆顶元素就是数组中的第 k 个最大元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;

        // 使用一个含有len个元素的最小堆，默认是最小堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // 把 len 个元素都放入一个最小堆中
        for(int i = 0;i < len;i++){
            minHeap.add(nums[i]);
        }

        // 然后再 pop() 出 len - k 个元素，此时最小堆只剩下 k 个元素
        for(int i = 0;i < len - k;i++){
            minHeap.poll();
        }

        // 堆顶元素就是数组中的第 k 个最大元素。
        return minHeap.peek();
    }
}
  • 思路 2：综合考虑以上两种情况，总之都是为了节约空间复杂度。即 k 较小的时候使用最小堆，k 较大的时候使用最大堆。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
import java.util.PriorityQueue;

public class Solution {

    // 根据 k 的不同，选最大堆和最小堆，目的是让堆中的元素更小
    // 思路 1：k 要是更靠近 0 的话，此时 k 是一个较大的数，用最大堆
    // 例如在一个有 6 个元素的数组里找第 5 大的元素
    // 思路 2：k 要是更靠近 len 的话，用最小堆

    // 所以分界点就是 k = len - k

    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        if (k <= len - k) {
            // System.out.println("使用最小堆");
            // 特例：k = 1，用容量为 k 的最小堆
            // 使用一个含有 k 个元素的最小堆
            PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, (a, b) -> a - b);
            for (int i = 0; i < k; i++) {
                minHeap.add(nums[i]);
            }
            for (int i = k; i < len; i++) {
                // 看一眼，不拿出，因为有可能没有必要替换
                Integer topEle = minHeap.peek();
                // 只要当前遍历的元素比堆顶元素大，堆顶弹出，遍历的元素进去
                if (nums[i] > topEle) {
                    minHeap.poll();
                    minHeap.add(nums[i]);
                }
            }
            return minHeap.peek();

        } else {
            // System.out.println("使用最大堆");
            assert k > len - k;
            // 特例：k = 100，用容量为 len - k + 1 的最大堆
            int capacity = len - k + 1;
            PriorityQueue<Integer> maxHeap = new PriorityQueue<>(capacity, (a, b) -> b - a);
            for (int i = 0; i < capacity; i++) {
                maxHeap.add(nums[i]);
            }
            for (int i = capacity; i < len; i++) {
                // 看一眼，不拿出，因为有可能没有必要替换
                Integer topEle = maxHeap.peek();
                // 只要当前遍历的元素比堆顶元素大，堆顶弹出，遍历的元素进去
                if (nums[i] < topEle) {
                    maxHeap.poll();
                    maxHeap.add(nums[i]);
                }
            }
            return maxHeap.peek();
        }
    }
}

解法二 ： 暴力

  • 最简单同时也一定是最容易编码的，编码成功的几率最高，可以用这个最简单思路编码的结果和其它思路编码的结果进行比对，验证高级算法的正确性；
  • 在数据规模小、对时间复杂度、空间复杂度要求不高的时候，简单问题简单做；

题目要求我们找到“数组排序后的第 k个最大的元素，而不是第 k个不同的元素” ，

  • 语义是从右边往左边数第 k个元素（从 1开始），那么从左向右数是第几个呢，我们列出几个找找规律就好了。
  • 一共 6 个元素，找第 2 大，索引是 44；
  • 一共 6个元素，找第 4 大，索引是 2。

因此，升序排序以后，目标元素的索引是 len - k。

1
2
3
4
5
6
7
8
9
10
import java.util.Arrays;

public class Solution {

    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        Arrays.sort(nums);
        return nums[len - k];
    }
}

复杂度分析

  • 时间复杂度：O(NlogN)，这里 NN 是数组的长度，算法的性能消耗主要在排序，JDK 默认使用快速排序，因此时间复杂度为 O(NlogN)。
  • 空间复杂度：O(1)，这里是原地排序，没有借助额外的辅助空间。

解法三 ： partition

  • 学习过 “快速排序” 的朋友，一定知道一个操作叫 partition，它是 “分而治之” 思想当中 “分” 的那一步。
  • 经过 partition 操作以后，每一次都能排定一个元素，并且这个元素左边的数都不大于它，这个元素右边的数都不小于它，并且我们还能知道排定以后的元素的索引。
  • 于是可以应用 “减而治之”（分治思想的特例）的思想，把问题规模转化到一个更小的范围里。

思路 ： 借助 partition 操作定位到最终排定以后索引为 len - k 的那个元素

快速排序虽然快，但是如果实现得不好，在遇到特殊测试用例的时候，时间复杂度会变得很高。如果你使用 partition 的方法完成这道题，时间排名不太理想，可以考虑一下是什么问题，这个问题很常见。

以下的描述基于 “快速排序” 算法知识的学习，如果忘记的朋友们可以翻一翻自己的《数据结构与算法》教材，复习一下，partition 过程、分治思想和 “快速排序” 算法的优化。

  • 分析：我们在学习 “快速排序” 的时候，接触的第 1 个操作就是 partition（切分），简单介绍如下：
  • partition（切分）操作，使得：
    • 对于某个索引 j，nums[j] 已经排定，即 nums[j] 经过 partition（切分）操作以后会放置在它 “最终应该放置的地方”；
    • nums[left]到 nums[j - 1] 中的所有元素都不大于nums[j]；
    • nums[j + 1]到 nums[right] 中的所有元素都不小于 nums[j]。

mark

  • partition（切分）操作总能排定一个元素，还能够知道这个元素它最终所在的位置，这样每经过一次 partition（切分）操作就能缩小搜索的范围，这样的思想叫做 “减而治之”（是 “分而治之” 思想的特例）。

  • 切分过程可以不借助额外的数组空间，仅通过交换数组元素实现

代码一 ： 正常的pivot

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {
    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;

        int left = 0;
        int right = len - 1;

        // 根据题意，第k大元素索引是len - k
        int target = len - k;

        while(true){
            int index = partition(nums,left,right);
            
            if(index == target){
                return nums[index];
            }else if(index < target){
                left = index + 1;
            }else{
                right = index - 1;
            }
        }
    }


    /**
    * 在数组 nums 的子区间 [left, right] 执行 partition 操作，返回 nums[left] 排序以后应该在的位置
    * 在遍历过程中保持循环不变量的语义
    * 1、[left + 1, j] < nums[left]
    * 2、(j, i] >= nums[left]
    *
    * @param nums
    * @param left
    * @param right
    * @return
    */
    private int partition(int[] nums,int left,int right){
        int pivot = nums[left];
        int j = left;

        for(int i = left + 1;i <= right;i++){
            if(nums[i] < pivot){
                // 小于pivot的元素都交换到pivot前面
                j++;
                swap(nums,j,i);
            }
        }

        // 在之前的遍历过程中，满足[left + 1,j] < pivot 并且 (j,i] >= pivot
        swap(nums,j,left);
        // 交换以后 [left, j - 1] < pivot, nums[j] = pivot, [j + 1, right] >= pivot
        return j;
    }

    private void swap(int[] nums,int index1,int index2){
        if(index1 == index2){
            return;
        }
        nums[index1] = nums[index1] ^ nums[index2];
        nums[index2] = nums[index1] ^ nums[index2];
        nums[index1] = nums[index1] ^ nums[index2];
    }
}

复杂度分析：

  • 时间复杂度：O(N)，这里 N 是数组的长度
  • 空间复杂度：O(1)，原地排序，没有借助额外的辅助空间。

代码二： random随机化pivot

注意：本题必须随机初始化 pivot 元素，否则通过时间会很慢，因为测试用例中有极端测试用例。

  • 为了应对极端测试用例，使得递归树加深，可以在循环一开始的时候，随机交换第 1个元素与它后面的任意 1 个元素的位置；

  • 说明：最极端的是顺序数组与倒序数组，此时递归树画出来是链表，时间复杂度是 O(N^2) 根本达不到减治的效果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
import java.util.Random;

public class Solution {

    private static Random random = new Random(System.currentTimeMillis());

    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        int target = len - k;
        int left = 0;
        int right = len - 1;
        while (true) {
            int index = partition(nums, left, right);
            if (index < target) {
                left = index + 1;
            } else if (index > target) {
                right = index - 1;
            } else {
                return nums[index];
            }
        }
    }

    // 在区间 [left, right] 这个区间执行 partition 操作

    private int partition(int[] nums, int left, int right) {
        // 在区间随机选择一个元素作为标定点
        if (right > left) {
            int randomIndex = left + 1 + random.nextInt(right - left);
            swap(nums, left, randomIndex);
        }

        int pivot = nums[left];
        int j = left;
        for (int i = left + 1; i <= right; i++) {
            if (nums[i] < pivot) {
                j++;
                swap(nums, j, i);
            }
        }
        swap(nums, left, j);
        return j;
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

代码三 : 使用双指针，将与 pivot 相等的元素等概论地分到 pivot 最终排定位置的两边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
import java.util.Random;

public class Solution {

    private static Random random = new Random(System.currentTimeMillis());

    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        int left = 0;
        int right = len - 1;

        // 转换一下，第 k 大元素的索引是 len - k
        int target = len - k;

        while (true) {
            int index = partition(nums, left, right);
            if (index == target) {
                return nums[index];
            } else if (index < target) {
                left = index + 1;
            } else {
                right = index - 1;
            }
        }
    }

    public int partition(int[] nums, int left, int right) {
        // 在区间随机选择一个元素作为标定点
        if (right > left) {
            int randomIndex = left + 1 + random.nextInt(right - left);
            swap(nums, left, randomIndex);
        }

        int pivot = nums[left];

        // 将等于 pivot 的元素分散到两边
        // [left, lt) <= pivot
        // (rt, right] >= pivot

        int lt = left + 1;
        int rt = right;

        while (true) {
            while (lt <= rt && nums[lt] < pivot) {
                lt++;
            }
            while (lt <= rt && nums[rt] > pivot) {
                rt--;
            }

            if (lt > rt) {
                break;
            }
            swap(nums, lt, rt);
            lt++;
            rt--;
        }

        swap(nums, left, rt);
        return rt;
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}
打赏
  • 版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！
  • © 2019-2022 Zhuuu
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信