首页 > 代码库 > 中国电信翼支付2014编程大赛决赛-一种排序 个人解题过程
中国电信翼支付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]){//获取乱序数组中的对应元素的位置，而且当前骨架的长度自增134 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
中国电信翼支付2014编程大赛决赛-一种排序 个人解题过程
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。