有趣的排序

题目
度度熊有一个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();
    }
}

有趣的排序

推荐阅读更多精彩内容