题目
度度熊有一个N个数的数组，他想将数组从小到大 排好序，但是萌萌的度度熊只会下面这个操作：
任取数组中的一个数然后将它放置在数组的最后一个位置。
问最少操作多少次可以使得数组从小到大有序？
输入描述：首先输入一个正整数N，接下来的一行输入N个整数。(N <= 50, 每个数的绝对值小于等于1000)
输出描述：输出一个整数表示最少的操作次数。
输入：
4
19 7 8 25
输出：
2
思路1
1）用一个辅助数组B，将原数组A中元素从小到大排序。
2）从数组B第一个元素开始，查找A中不需要移动的元素。假设A为[3,5,4,2,3,7]，则B为[2,3,3,4,5,7]，则原数组A除2,3（第二个3）不需要移动外，其余元素都需要移动，操作次数=数组大小-不需要移动的元素个数（即4=6-2）
代码1
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int[] array = new int[n];
int[] array1 = new int[n];
while(scan.hasNext()){
for(int i=0;i<n;i++){
array[i] = scan.nextInt();
array1[i] = array[i];
}
Arrays.sort(array1);
int count = 0;
int index = 0;
for(int i=0;i<n;i++){
if(array1[index] == array[i]){
count++;
index++;
}
}
System.out.println(n-count);
}
scan.close();
}
}
思路2
1）运用map，将元数组存入map中，map的key存储array[i]，value存储i。
2）将数组array从小到大排序，排序后，array[i]<=array[i+1]。
3）若map.get(array[i])>map.get(array[i+1])，则表示在待排序数组中，array[i+1]在array[i]的前面，必须将arr[i+1]移动到最后的位置，更新map中array[i+1]对应的value值。
代码2
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int[] array = new int[n];
while(scan.hasNext()){
for(int i=0;i<n;i++){
array[i] = scan.nextInt();
}
Map<Integer,Integer> map = new HashMap<Integer, Integer>();
for(int i=0;i<n;i++){
map.put(array[i], i); //map的key存储array[i],value存储i;
}
Arrays.sort(array);
int count = 0;
int index = n;
for(int i=0;i<n-1;i++){
// array已经排序，故array[i]<=array[i+1],
// 若map.get(array[i])>map.get(array[i+1]),
//则表示在待排序数组中，array[i+1]在array[i]的前面
if(map.get(array[i])>map.get(array[i+1])){
count ++;
map.put(array[i+1], map.size()+index);
index++;
}
}
System.out.println(count);
}
scan.close();
}
}
