[关闭]
@Aqua-Dream 2016-10-19T01:30:12.000000Z 字数 2950 阅读 1087

浙大PAT-Sort with Swap(0, i)

算法


来自ZJU数据结构基础的习题。

Given any permutation of the numbers {0, 1, 2,…, N−1}, it is easy to sort them in increasing order. But what if Swap(0, *) is the ONLY operation that is allowed to use? For example, to sort {4, 0, 2, 1, 3} we may apply the swap operations in the following way:

Swap(0, 1) => {4, 1, 2, 0, 3}
Swap(0, 3) => {4, 1, 2, 3, 0}
Swap(0, 4) => {0, 1, 2, 3, 4}

Now you are asked to find the minimum number of swaps need to sort the given permutation of the first N nonnegative integers.

Input Specification:
Each input file contains one test case, which gives a positive N(≤105) followed by a permutation sequence of {0, 1, …, N−1}. All the numbers in a line are separated by a space.

Output Specification:
For each case, simply print in a line the minimum number of swaps need to sort the given permutation.

Sample Input:
10
3 5 7 2 6 4 9 0 8 1

Sample Output:
9

题目意思是,给定一串由0,1,2,…,N-1重新排列而成的数,只通过交换0与某一个数这样的操作,最后将数列排列为0,1,2,…,N-1。让你编一个程序,接收给定的数列,输出排列结束所需最少的交换次数。C++代码我放在最后,这里撇开程序,集中讨论解决这个问题的方法。

的一个置换,交换0与称为一次交换操作,下面将给出把利用交换操作变成所需的最小操作次数以及具体方法。

用表格记录置换如下:

0 1 2

把表格中规定的对应关系记为,那么给出了0到的一个置换。

现在对于,构造数据链,那么容易发现,这是一条周期链,且在同一个周期内无重复元素。记最小正周期为,就是说数据构成一个圆环,环中元素互不相同,。不仅如此,定义一个关系~,如果a,b同属于某个链,那么~。可以证明,~是一个等价关系。数据0到~分成了许多等价类。

举个例子:现在,数据列为3 5 7 2 6 4 9 0 8 1 (就是示例),按上面的描述,可以填出表格:

0 1 2 3 4 5 6 7 8 9
3 5 7 2 6 4 9 0 8 1


从0开始构造数据链:

0->3->2->7->(0)
1->5->4->6->9->(1)
8->(8)

在同一个链中的元素,就认为是互相等价的。那么在此例中,0到,就被分成了3个等价类。从单个的意义来说,等价类的各个元素都完全对称。

现在我们从等价类的角度来看一般的交换操作。设swap(i,j)表示交换数据,的操作,具体到表格中就是交换的值。假设同属一个等价类,那么不难证明,交换之后链被分成两个(分别含有的链),例如1->5->4->6->9->(1)中,交换1和6,那么新的为原来的,即9,所以包含1的链为1->9->(1),类似地,包含6的链为6->5->4->(6)。如果不属一个等价类,那么不难证明,swap(i,j)导致两条链合并成一条。例如0->3->2->7->(0)1->5->4->6->9->(1),交换7和5,链变成7->4->6->9->1->5->0->3->2->(7)

我们最终的目的,是要通过0与其他元素的交换,将0到分成个互不相同的等价类。具体到本题,我们需要关注等价类中的两个性质,一是有没有0,二是环中元素共多少个。为了把一个长度为()(这里的长度指的是链的周期)的、不含0的链分成个链,我们至少需要进行次交换操作,即将0所在链与其合并得到一个长度至少为的链,然后进行至少次断链操作。而对于0所在长度为的链,至少需要次断链操作才能分成个等价类。这样一来,我们就得到最小操作次数的一个下界。

事实上这个下界可以用这样的方法取到:将0所在链断成若干个单元素等价类,然后将0元素与其他非单元素链合并,再重复上述操作,除非找不到其他单元素链,这时任务完成。实际上,这就是代码所蕴含的思路。

以示例为例:

0->3->2->7->(0)
1->5->4->6->9->(1)
8->(8)

交换0与3(交换1次),得到

0->2->7->(0)
1->5->4->6->9->(1)
8->(8)
3->(3)

依次交换0与2,7(累计交换3次),得到

0->(0)
1->5->4->6->9->(1)
8->(8)
3->(3)
2->(2)
7->(7)

也就是说,依次将0与,,…直到0的元素进行交换,可以把0所在链给完全断开。

交换0与1(累计交换4次),得到

0->5->4->6->9->1->(0)
8->(8)
3->(3)
2->(2)
7->(7)

这一操作把单元素链0与其他非单元素链组合起来。

再依次交换0与5,4,6,9,1(累计交换9次),即可完成任务。这样一来,交换次数为9,即为所求。

下面是该问题的C++代码解,时间和空间复杂度都是O(n)。注释我就没写了,因为网上可以搜到相同思路的代码,只是没有像上面一样给出一个比较完善的证明。

  1. #include <iostream>
  2. using namespace std;
  3. int search(int* p, int num)
  4. {
  5. static int first = 1;
  6. for (int i = first; i<num; i++)
  7. if (p[i] != i)
  8. return first = i;
  9. return 0;
  10. }
  11. void swap(int* p, int n)
  12. {
  13. int temp = p[0];
  14. p[0] = p[n];
  15. p[n] = temp;
  16. }
  17. int main()
  18. {
  19. int n;
  20. cin >> n;
  21. int *data = new int[n];
  22. int temp;
  23. for (int i = 0; i<n; i++)
  24. {
  25. cin >> temp;
  26. data[temp] = i;
  27. }
  28. int count = 0;
  29. while (true)
  30. {
  31. if (data[0])
  32. swap(data, data[0]);
  33. else
  34. {
  35. temp = search(data, n);
  36. if (!temp) break;
  37. swap(data, temp);
  38. }
  39. count++;
  40. }
  41. cout << count << endl;
  42. delete[] data;
  43. return 0;
  44. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注