Fork me on GitHub

PAT(甲级)渡劫(二十五)-Sort with Swap(0,*) (25)


PAT(甲级)渡劫(二十五)-Sort with Swap(0,*) (25)

算法思想:

贪心算法

次数最少的方法,即:
1.每次都将0与应该放置在0位置的数字交换即可。
2.如果0处在自己位置上,那么随便与一个不处在自己位置上的数交换,重复上一步即可。
拿样例举例:
0 1 2 3 4 5 6 7 8 9
0:3 5 7 2 6 4 9 0 8 1

1:3 5 0 2 6 4 9 7 8 1
2:3 5 2 0 6 4 9 7 8 1
3:0 5 2 3 6 4 9 7 8 1 (如果0处在自己位置上,那么找一个不在自己位置上的数val与之交换)
4:5 0 2 3 6 4 9 7 8 1
5:5 1 2 3 6 4 9 7 8 0
6:5 1 2 3 6 4 0 7 8 9
7:5 1 2 3 0 4 6 7 8 9
8:5 1 2 3 4 0 6 7 8 9
9:0 1 2 3 4 5 6 7 8 9

在例子第3步交换中,如果每次都线性查找,时间复杂度就会很高,会有2组样例超时。
这里用set优化了下速度。

代码如下:

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
#include <iostream>
#include <cstdio>
#include <set>

using namespace std;
const int maxn = 100000+5;
int a[maxn];
int pos[maxn];
set<int> leftnum; // 存储了还没有被放到正确位置上的数字(0除外)
int cnt;
int main(){
freopen("in.txt","r",stdin);
int n;
scanf("%d",&n);
cnt = n; // 还未排好序的个数
for(int i = 0 ; i < n ; i++){
scanf("%d",&a[i]);
pos[a[i]] = i; // 存储每个数字的下标
if(i == a[i])
cnt--; // 该数已在正确位置
else if(a[i] != 0)
leftnum.insert(a[i]);
}
int p0 = pos[0]; // 0目前所在的位置或应该交换的数
int p;
int ans = 0;
while(cnt){
// 将0和应处在0位置的数(p0)交换位置
a[p0] = p0;
leftnum.erase(p0);
p0 = pos[p0];
ans++;
cnt--;
if(p0 == 0)
cnt--;
// 如果0在自己的位置上,但还没有排好序
if(p0 == 0 && cnt){
// 这里用set来优化寻找还没有处在自己位置的数字,将0与之交换
int val = *leftnum.begin();
int temp = pos[val];
pos[val] = p0;
a[p0] = val;
p0 = temp;
a[p0] = 0;
ans++;
cnt++; // 之前多减了一次
}
}
printf("%d",ans);
return 0;
}

运行结果:

坚持原创技术分享,您的支持将鼓励我继续创作
-------------本文结束感谢您的阅读-------------
0%