考研笔记

板子：partition 的应用（第 k 小、2016 集合划分、按条件划分）

一次划分之后，枢轴左边都不比它大、右边都不比它小。只往答案所在的那一边继续划分，平均 就能找到第 小，不用把整个数组排好序。

第 k 小与 2016 集合划分

int kthSmallest(int A[], int n, int k) {     // 第 k 小（k 从 1 开始）；会打乱 A 的顺序
    int low = 0, high = n - 1;               // 第 k 小最终会落在下标 k-1，它始终在 [low, high] 里
    while (true) {
        int p = Partition(A, low, high);     // 枢轴落在 p：它就是第 p+1 小
        if (p == k - 1) return A[p];         // 正好是要找的
        if (p < k - 1) low = p + 1;          // 答案在右边
        else high = p - 1;                   // 答案在左边
    }
}
 
int setPartition(int A[], int n) {           // 2016：n 个正整数分成 A1、A2，返回 S2 - S1 的最大值
    int k = n / 2;                           // A1 放最小的 ⌊n/2⌋ 个，这样 |n1-n2| 最小、|S1-S2| 最大
    kthSmallest(A, n, k);                    // 做完以后，A[0..k-1] 就是最小的 k 个（内部不一定有序）
    int s1 = 0, s2 = 0;
    for (int i = 0; i < k; i++) s1 += A[i];  // A1 = A[0..k-1]
    for (int i = k; i < n; i++) s2 += A[i];  // A2 = A[k..n-1]
    return s2 - s1;
}

Partition 就是 快速排序 那一篇的教材版。

复杂度：平均时间 ，最坏 ；空间 。

按条件划分（一趟扫描、原地交换）

void oddFirst(int A[], int n) {              // 把所有奇数移到偶数前面
    int i = 0, j = n - 1;
    while (i < j) {
        while (i < j && A[i] % 2 != 0) i++;  // 从前往后找第一个偶数
        while (i < j && A[j] % 2 == 0) j--;  // 从后往前找第一个奇数
        if (i < j) { int t = A[i]; A[i] = A[j]; A[j] = t; }   // 交换：奇数换到前面
    }
}
 
void dutchFlag(int A[], int n) {             // 荷兰国旗：0 放前面、1 放中间、2 放后面
    int i = 0, j = 0, k = n - 1;             // A[0..i-1] 全是 0，A[i..j-1] 全是 1，A[k+1..n-1] 全是 2
    while (j <= k) {                         // A[j..k] 是还没看过的部分
        if (A[j] == 0) {                     // 0：换到 0 区的末尾，i、j 都后移
            int t = A[i]; A[i] = A[j]; A[j] = t;
            i++; j++;
        } else if (A[j] == 2) {              // 2：换到 2 区的前面，k 前移；换过来的还没看，j 不动
            int t = A[j]; A[j] = A[k]; A[k] = t;
            k--;
        } else j++;                          // 1：本来就在中间，不动
    }
}

复杂度：都是一趟扫描，时间 ，空间 。

考场答案要点（2016）

  • 题意： 个正整数分成两个子集 、，要求 最小、 最大。
  • （1）设计思想：把最小的 个数放进 ，其余放进 。仿照快速排序做划分：枢轴落位后，如果它就是第 小，就结束；否则只对包含该位置的那一段继续划分。不需要把整个数组排好序。
  • （3）复杂度：平均时间 ，空间 。

关键边界

位置为什么
目标下标是 k - 1第 小在排好序的数组里下标是 （下标从 0 开始）
low = p + 1 / high = p - 1枢轴已经确定不是答案，下一次划分不包括它。区间每次至少缩小 1，一定会结束
dutchFlag 换来 2 以后 j 不动从 A[k] 换过来的元素还没看过，要在下一轮判断它
dutchFlag 换来 0 以后 j 可以后移从 A[i] 换过来的一定是 1（或者 i == j 时就是它自己），已经看过了

易错点

  • 2016 年排序后再取前一半也是正确解，但时间是 ，不如划分法优。
  • oddFirst 对负数也成立：-3 % 2 等于 ，不等于 0，所以仍然判为奇数。

链接

反向链接