微软2014实习生及秋令营技术类职位在线测试: Reduce inversion count

import java.util.Scanner;

public class ReduceInversionCount {


	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);
		String inStr ;
		Integer[] num ;
		while(in.hasNext()){
			inStr = in.nextLine();
			num = tranString2IntArr(inStr);
			
			int count = inversionCount(num, num.length);
			if(count == 0){System.out.println(0);continue;}
			for(int i = 0 ;i < num.length ; i++){
				for(int j = i+1 ; j < num.length ; j++){
					if(num[i] > num[j]){ //发现逆序对
						swap(num,i,j);
						int tempcount = inversionCount(num, num.length);
						count = count < tempcount ?count:tempcount;
						swap(num,i,j);
					}
				}
			}
			
			System.out.println(count);
		}
	}

	private static void swap(Integer[] num, int i, int j) {

		int temp = num[i];
		num[i] = num[j];
		num[j] =temp;
	}

	private static Integer[] tranString2IntArr(String inStr) {
		String[] strs = inStr.split(",");
		Integer result[] = new Integer[strs.length];
		for(int i = 0 ;i < strs.length ; i++)
			result[i] = Integer.parseInt(strs[i]);
		return result;
	}

	private static int inversionCount(Integer[] num,int n){
		int count = 0 ;		
		for(int i = 0 ;i < n ;i++)
			for(int j = i+1 ;j < n; j++)
				if(num[i] > num[j]) count++;
		return count ;
	}
}

微软2014实习生及秋令营技术类职位在线测试: Reduce inversion count,布布扣,bubuko.com

微软2014实习生及秋令营技术类职位在线测试: Reduce inversion count

原文：http://blog.csdn.net/yunshuixiliu/article/details/23593177