中国电信翼支付2014编程大赛决赛-一种排序 个人解题过程

首先需要表明的是我在时限内想到这个解法,但是这个解法被判错,而我也想不到反例赛后咨询举办方的时候,他们表示过几天会发测试数据给我们。所以今天就先把思路和代码先放上来,过几天收到数据再看看到底哪里错了。
如果有读者想到相应的反例,希望可以给我留言,谢谢。
 
题目详情(只限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 

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。