中国电信翼支付2014编程大赛决赛-一种排序 个人解题过程
浏览数：32 /
时间：2015年06月11日
首先需要表明的是我在时限内想到这个解法，但是这个解法被判错，而我也想不到反例。赛后咨询举办方的时候，他们表示过几天会发测试数据给我们。所以今天就先把思路和代码先放上来，过几天收到数据再看看到底哪里错了。
如果有读者想到相应的反例，希望可以给我留言，谢谢。
题目详情（只限Java）
给定一串整数，你只能进行两种操作：任选一个整数放到这串数之前，或者这串之后。所有的整数都不相等。
问把这串整数变为由小到大的排好序最少需要的操作次数。
输入格式：
多组数据，每组数据1行，包含若干个空格分隔的非负整数，每个整数不超过2147483647。
输出格式：
每组数据输出一行包含一个整数，表示需要最少操作的次数。
答题说明
输入样例
1 2 3
1 4 2
10 2 1
输出样例：
0
1
2
个人解题思路：
假设给定的乱序数组为a[]=[1,4,2,8]，则使用容器排序后可得到顺序数组，同时也是目标数组b[]=[1,2,4,8]。
那么我们就通过用b的连续子数组（如[1,2,4], [2,4,8], [1,2]以及[4,8]之类的，就是元素必须是在顺序数组中位置连续的）去a中匹配，然后获取最长的那个连续子数组的长度为length，然后乱序数组的长度减去length就可以得到需要操作的最少次数。
（注：我其实并不是很熟练算法，所以以下代码是没有经过特别大的时间复杂度/空间复杂度优化的）
Java代码如下：
1 import java.util.*;
2
3 public class Main{
4
5 public static void main(String[] args) {
6 // TODO 自动生成的方法存根
7 //我这道题的解题思路是找乱序的数组和排好序的数组的最长骨架，然后操作次数就是数组长度减去骨架数组的长度。
8 //举个例子，乱序数组a=[1,4,2,8],顺序数组b=[1,2,4,8]，那么我就用顺序数组的第一个元素在乱序数组中开始找起，
9 //找到b[0]==a[0],骨架数组为[1]然后用b[1]去a中从a[1]开始遍历到a[3]，发现b[1]==a[2],骨架数组变为[1,2]，
10 //然后拿b[2]去a中从a[3]开始遍历到a[3]，发现没有相等的，骨架生成完毕，骨架数组的长度为2，那么以b[0]为首的骨架数组就生成完毕，
11 //接着同样道理，以b[2]为首开始去a中从a[0]开始遍历建立骨架，最后建立出以b[2]为首的骨架数组[4,8]，其长度为2。
12 //这样b中的全部元素都被包含在骨架中了，此时取得最长骨架的长度，此处为2，原数组长度为4，则需要操作的次数则为4-2=2次。
13 Scanner sc = new Scanner(System.in);
14 while(sc.hasNext()){
15 List<Integer> data_sorted = new ArrayList<Integer>();
16 String line = sc.nextLine();
17 String[] dataS = line.split(" "); //读入一行数据后切分
18 int[] dataD = new int[dataS.length];
19 int[] dataD_S = new int[dataS.length];
20 for(int i = 0;i<dataS.length;i++){ //把数据转换成int型，同时把数据加入到容器中
21 dataD[i] = Integer.parseInt(dataS[i]);
22 data_sorted.add(dataD[i]);
23 }
24 Collections.sort(data_sorted); //把容器中的数据排序
25 for(int i = 0;i<dataS.length;i++){ //获取排好序的数据数组
26 dataD_S[i] = data_sorted.get(i);
27 }
28 boolean flag = true;
29 int length = 0; //骨架长度
30 for(int i=0;i<dataD.length;i++){ //从排好序的数组的首位开始找起
31 int startR=0,tLength=0; //乱序数组中的对应元素的位置以及当前骨架的长度
32 for(int j=0;j<dataD.length;j++){
33 if(dataD[j]==dataD_S[i]){//获取乱序数组中的对应元素的位置，而且当前骨架的长度自增1
34 startR = j;
35 tLength++;
36 break;
37 }
38 }
39 for(int j=i+1;j<dataD.length;j++){
40 if(!flag){
41 break;
42 }
43 boolean tB = false;
44 for(int k = startR+1;k<dataD.length;k++){
45 if(dataD_S[j]==dataD[k]){
46 tLength++;
47 startR=k;
48 flag = true;
49 break;
50 }
51 if(k==dataD.length-1){ //如果搜完乱序数组的后面的元素都没找到对应的，则设置标志位跳出本次循环
52 flag = false;
53 i = j-1; //顺序数组中从i到j-1的元素都已经包含在了当前骨架中，所以下一个骨架的首部应该是第j个元素
54 }
55 }
56 }
57 length = length>tLength?length:tLength; //取已有骨架中最长的骨架的长度
58 flag = true; //初始化标志位
59 }
60 System.out.println(dataD.length-length); //输出差值作为结果
61 }
62 sc.close();
63 }
64 }
原文：http://www.cnblogs.com/shawlaw/p/2014_chinanet_final_contest.html
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
