最小排序（美团点评）

输入两行数字，第一行表示第二行的个数 n，第二行看做 这n个数的排列，如下所示：

4

2 1 3 4

要求对第二行数组进行一次操作，使操作后的排列最小，注意：至少且仅此操作一次。

解答：刚开始没有注意到必须进行一次操作，只用一个min用来记录最小数字的下标，但是题目要求操作一次，如果输入的排列的第一个数是最小的，那么就没有对该排列 进行操作，显然是不符合题意的。后来又增加了一个next，用来记录第二小的数字的下标，当第一个数是最小数时，就将第一个数与第二个数进行交换位置，但是程序的通过率并没有提高，只有20%，想了好久，发现我的第二个最小的数有问题，例如，输入6个数：1 2 1 3 2 1，我的程序会将下标为0的数字与下标为5的数字进行交换，得到1 2 1 3 2 1， 但是这并不是一步交换可以得到的最小的排列，最小的排列应该是1 1 1 3 2 2 。

后来的想法是：先扫描一次数组，用index指向当前第一个数，如果当前的第一个数不是最小的，那么就将最小的数字和第一个位置上数交换，结束。如果当前的第一个数是最小的，则将index加1，判断第二个数是不是最小的，依次判断，直到下标移动到最后一个数。当下标移动到最后一个数时，说明数组是递增排序的，那么应该将最后两个数进行交换，这样得到的交换后的数最小。

public static ArrayList<Integer> MinOrder(ArrayList<Integer> list){
  if(list==null || list.size()==0){
   return null;
  }
  int min=0,index=0; //index表示当前的第一个数的下标，min表示在当前第一个数开头的数组中的最小数的下标
  while(index<list.size()){
   	for(int i=index;i<list.size();i++){
    		if(list.get(i)<list.get(index)){ //当前index指向的数不是最小的数，用min记录下最小数的下标
    			 min=i;
    		}
  	 }
  	 if(min==index){ //当前index指向的数是最小的数，那么就排除当前的数，说明应该交换的位置在后面
    		index++;
   		 min++;
  	 }else{
   		 int temp=list.get(min);
   		 list.set(min, list.get(index));
    		list.set(index, temp);
    		return list;
  	 }
   }
   if(index>=list.size()){  //说明数组单调递增，直接交换最后两个数
         int temp=list.get(list.size()-1);
   	 list.set(list.size()-1, list.get(list.size()-2));
   	 list.set(list.size()-2, temp);
    }
  return list;
 }	
           

测试数据

4

2 1 3 4

输出 1 2 3 4 

6

1 1 2 3 1 1 

输出 1 1 1 3 1 2 

4 

1 1 2 3 

输出 1 1 3 2 

因为这是在笔试结束后才想到的，所以没有办法去测试程序是否能够达到AC，希望看到的这篇博客的朋友，如果发现有不满足的用例，或对解法提出质疑的，都真切的希望能在评论区提出你们的想法，谢谢！