考研算法辅导课笔记（十七）

真题讲解

2011-11

解答：

up操作，比较2次，第一次交换元素，第二次不交换。

2012-10

按照王道的快排写法，每一轮排序可以确定基准元素的最终位置。以王道为准。

答案选A。

2012-11

答案选D。

折半相对直接插入优化了比较（查找）次数。

2013-11（手动模拟）

答案选C。

如果不说明转化为多少进制，默认为10进制。

从低位关键字开始排序，用代码跑一遍验证一下。

i = 1:
110 120 911 122 114 7 119 // 按个位排序，0 0 1 2 4 7 9
i = 2:
7 110 911 114 119 120 122 // 按十位排序，0 1 1 1 1 2 2

注意双关键字排序的误区：

第二轮排序并不是在个位关键字相同的部分中再进行十位关键字排序。

而是在第一轮排序的基础上对于整个数组进行十位关键字排序！

2014-10

答案选B。

希尔排序也就是递减增量排序算法。

看看是否增量对应的每个子序列都有序就可确认增量是否合理。

2014-11

常考题型。

快排以教材写法为准。

答案选C。只有1个元素在最终位置上。

做法：根据选项数一下有多少元素在正确位置（左边都比它小且右边都比它大）上。

2015-9

答案选C。

基数排序是非比较类排序，时间复杂度和关键字序列无关。

2015-10

答案选C。

删掉堆顶，然后堆尾移到堆顶，执行down操作。

acwing.1603. 整数集合划分（PAT甲级真题，考研408真题）

给定一个包含 N 个正整数的集合，请你将它划分为两个集合 A1 和 A2，其中 A1 包含 n1 个元素，A2 包含 n2 个元素。
集合中可以包含相同元素。
用 S1 表示集合 A1 内所有元素之和，S2 表示集合 A2 内所有元素之和。
请你妥善划分，使得 |n1−n2| 尽可能小，并在此基础上 |S1−S2| 尽可能大。

输入格式
第一行包含整数 N。
第二行包含 N 个正整数。

输出格式
在一行中输出 |n1−n2| 和 |S1−S2|，两数之间空格隔开。

数据范围
2≤N≤10^5,
保证集合中各元素以及所有元素之和小于 2^31。

输入样例1：
10
23 8 10 99 46 2333 46 1 666 555
输出样例1：
0 3611
输入样例2：
13
110 79 218 69 3721 100 29 135 2 6 13 5188 85
输出样例2：
1 9359

思路1：

利用堆排序（大根堆）找出前k大的元素。

如果集合个数为偶数，那么|n1−n2|为0，两个集合个数都为n/2，一半取到前n/2大的元素；

如果集合个数为奇数，那么|n1−n2|为1，两个集合个数分别为n/2和n/2 + 1，大集合取前n/2 + 1大的元素。

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N],n;

void down(int a[],int u,int len){
    int t = u;
    if (2*u <= len && a[2*u] > a[t]) t = 2*u;
    if (2*u+1 <= len && a[2*u+1] > a[t]) t = 2*u+1;
    if (t != u){
        swap(a[u],a[t]);
        down(a,t,len);
    }
}

int heap_sort(int a[],int n){
    int len = n; // len维护堆的大小，范围：1~len
    int k = n % 2 ? n/2 + 1 : n/2;
    for (int i = n/2; i; i --) down(a,i,len); // 建堆
    
    int res = 0;
    for (int i = 0;i < k;i ++){ // k轮，每一轮操作找到最大的一个数
        // 注意顺序不要写反，先把堆顶换下来，然后删掉末尾，down堆顶
        res += a[1];
        swap(a[1],a[len]);
        len --;
        down(a,1,len);
    }
    return res;
}

int main(){
    cin >> n;
    
    int sum = 0;
    for (int i = 1;i <= n;i ++){
        cin >> a[i]; // 注意下标从1开始
        sum += a[i];
    }
    
    int max_sum = heap_sort(a,n);
    
    cout << (n % 2 ? 1 : 0) << ' ' << 2*max_sum - sum << '\n';
    return 0;
}

思路2：

直接sort。

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N],n;

int main(){
    cin >> n;
    
    for (int i = 0;i < n;i ++) cin >> a[i];
    
    sort(a,a + n);
    
    int max_sum = 0,min_sum = 0;
    for (int i = 0;i < n/2;i ++) min_sum += a[i]; // 不管奇数还是偶数，n/2一定是小集合
    for (int i = n/2;i < n;i ++) max_sum += a[i];
    
    cout << (n % 2 ? 1 : 0) << ' ' << max_sum - min_sum << '\n';
    return 0;
}

2017-11

如果排序涉及到随机索引操作，则时间效率会降低。

答案选D。

希尔排序会偏移增量进行索引，堆排序down，up操作会进行随机索引。

2018-10

答案选D。

看看是否增量对应的每个子序列都有序就可确认增量是否合理。

2018-11

答案选A。

建堆思路：从n/2处一直到1号点执行down操作。手动模拟。

2019-10

快排以教材写法为准。

答案选C。只有1个元素在最终位置上。

做法：根据选项数一下有多少元素在正确位置（左边都比它小且右边都比它大）上。

按照题目意思，第一趟确定一个最终位置，第二趟左右两部分都需要确定一个最终位置（如果这部分存在）。

注意基准点取在端点的情况。

答案选D。

2019-11

我们先取掉x个数（补上k-x个 0），x = (n-1) % (k-1) = 119 % 11 = 9，所以补充2个虚段。

答案选B。

2020-9

考察堆的基本概念。

答案选1,2,4。

2020-11

考虑极端情况，对于完全有序的数组，直接插排和选择排序移动次数相同。移动次数不一定。

只有1是对的。答案选A。

acwing.3874. 三元组的最小距离（2020考研408真题）

定义三元组 (a,b,c)（a,b,c 均为整数）的距离 D=|a−b|+|b−c|+|c−a|。
给定 3 个非空整数集合 S1,S2,S3，按升序分别存储在 3 个数组中。
请设计一个尽可能高效的算法，计算并输出所有可能的三元组 (a,b,c)（a∈S1,b∈S2,c∈S3）中的最小距离。
例如 S1={−1,0,9},S2={−25,−10,10,11},S3={2,9,17,30,41} 则最小距离为 2，相应的三元组为 (9,10,9)。

输入格式
第一行包含三个整数 l,m,n，分别表示 S1,S2,S3 的长度。
第二行包含 l 个整数，表示 S1 中的所有元素。
第三行包含 m 个整数，表示 S2 中的所有元素。
第四行包含 n 个整数，表示 S3 中的所有元素。
以上三个数组中的元素都是按升序顺序给出的。

输出格式
输出三元组的最小距离。

数据范围
1≤l,m,n≤10^5,
所有数组元素的取值范围 [−10^9,10^9]。

输入样例：
3 4 5
-1 0 9
-25 -10 10 11
2 9 17 30 41
输出样例：
2

有一定难度。

思路：

容易发现三元组的距离其实就是三个数中的最大值与最小值的差的两倍。

求三元组最小距离就是合并三个有序数组，在整个数组中找到包含三个数组中各自的至少一个元素的一段区间，枚举这段区间找最小距离。

借用归并排序的思想，用三指针分别扫描三个数组，找到三指针对应的最小值，和最大值，计算一个三元组距离，然后最小值对应指针向前移动，求出最小三元组距离。

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5+5;
int a[N],b[N],c[N];
int l,m,n;

int main(){
    cin >> l >> m >> n;
    
    for (int i = 0;i < l;i ++) cin >> a[i];
    for (int i = 0;i < m;i ++) cin >> b[i];
    for (int i = 0;i < n;i ++) cin >> c[i];
    
    LL res = 1e12; // 三指针扫描，res取一个很大的数
    for (int i = 0,j = 0,k = 0;i < l && j < m && k < n;){
        int x = a[i],y = b[j],z = c[k];
        
        res = min(res,2*((LL)max(max(x,y),z) - min(min(x,y),z)));
        if (x <= y && x <= z) i ++;
        if (y <= x && y <= z) j ++;
        if (z <= x && z <= y) k ++;
    }
    
    cout << res << '\n';
    return 0;
}

2013-41

acwing.52. 数组中出现次数超过一半的数字（剑指Offer）

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
假设数组非空，并且一定存在满足条件的数字。

思考题：
假设要求只能使用 O(n) 的时间和额外 O(1) 的空间，该怎么做呢？
    
数据范围
数组长度 [1,1000]。

样例
输入：[1,2,1,1,3]
输出：1

考察摩尔投票法。

代码很短，难度很高。（y总评价）

题解一：排序，主元素一定在一半的位置出现。

时间复杂度：O(n*logn)，空间复杂度：O(logn)。

class Solution {
public:
    int moreThanHalfNum_Solution(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        return nums[nums.size()/2];
    }
};

题解二：摩尔投票法。

算法步骤

我们维护一个局部变量作为当前查找元素，一个局部变量作为计数器，

当遍历开始的时候，此时计数（count）为0，则将数组第一个元素作为当前查找元素；

当遍历的元素与查找元素相等，计数加1；反之则-1；

若当计数为0时，将下一个元素作为当前查找元素，继续重复以上操作；当遍历结束时，当前查找元素则为目标元素。

反证法证明摩尔投票法的正确性。

注意：如果序列中没有这种元素，算法不能检测到正确结果，将输出其中的一个元素之一。

摩尔投票法需要满足两个先决条件：

1、出现超过一半以上(n/2)的元素有且只有一个；

2、这个元素一定存在。

如果不能保证输入数据中有占有一半以上的元素，需要再遍历一下验证。（本题保证有解）

形象化理解：

	核心就是对拼消耗。
    玩一个诸侯争霸的游戏，假设你方人口超过总人口一半以上，并且能保证每个人口出去干仗都能一对一同归于尽。最后还有人活下来的国家就是胜利。那就大混战呗，最差所有人都联合起来对付你（对应你每次选择作为计数器的数都是众数），或者其他国家也会相互攻击（会选择其他数作为计数器的数），但是只要你们不要内斗，最后肯定你赢。最后能剩下的必定是自己人。

作者：知乎用户
链接：https://www.zhihu.com/question/49973163/answer/617122734
来源：知乎

class Solution {
public:
    int moreThanHalfNum_Solution(vector<int>& nums) {
        int cnt = 0,val; // cnt表示计数器，val表示集合中的当前元素
        for (auto x : nums){
            if (!cnt) val = x,cnt ++; // 如果集合中元素都牺牲了，val占据集合
            else if (val == x) cnt ++; // 如果新加入的是自己人，计数器 ++
            else cnt --; // 如果新加入的是敌人，计数器 --
        }
        
        cnt = 0; // 验证是否存在解，本题保证有解可以不用验证
        for (auto x : nums){
            if (x == val) cnt ++;
        }
        if (cnt <= nums.size()/2) return -1;
        return val;
    }
};