首页 > 数据结构 > Hash表 > POJ 1674 Sorting by Swapping [解题报告] Java
2013
11-10

POJ 1674 Sorting by Swapping [解题报告] Java

Sorting by Swapping

问题描述 :

Given a permutation of numbers from 1 to n, we can always get the sequence 1, 2, 3, …, n by swapping pairs of numbers. For example, if the initial sequence is 2, 3, 5, 4, 1, we can sort them in the following way:

2 3 5 4 1

1 3 5 4 2

1 3 2 4 5

1 2 3 4 5

Here three swaps have been used. The problem is, given a specific permutation, how many swaps we needs to take at least.

输入:

The first line contains a single integer t (1 <= t <= 20) that indicates the number of test cases. Then follow the t cases. Each case contains two lines. The first line contains the integer n (1 <= n <= 10000), and the second line gives the initial permutation.

输出:

For each test case, the output will be only one integer, which is the least number of swaps needed to get the sequence 1, 2, 3, …, n from the initial permutation.

样例输入:

2
3
1 2 3
5
2 3 5 4 1

样例输出:

0
3

解题代码:

//* @author: [email protected]
import java.io.*;
import java.util.*;
public class Main
{
 public static void main(String[] args) throws IOException
 {
  InputStreamReader is=new InputStreamReader(System.in);
  BufferedReader in=new BufferedReader(is);
  String[] ss;
  int a=Integer.parseInt(in.readLine());
  HashSet< Integer> hs=new HashSet< Integer>();
  while((a--)!=0)
  {
	int b=Integer.parseInt(in.readLine());
	ss=in.readLine().split(" ");
	int[] arr=new int[b+1];
	for(int i=0;i< b;i++)
		arr[i+1]=Integer.parseInt(ss[i]);
	int c=0;
	for(int i=1;i<=b;i++)
	{
         int u=arr[i];
	if(!hs.contains(u))
	{
	 while(!hs.contains(u))
	  {
		hs.add(u);
		u=arr[u];
	   }
	   c++;
	 }
       }
	System.out.println(b-c);
	hs.clear();
    }
  }		
}

  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。