阿里云开发者社区在线编程86.完美排列

微wx笑 2020-07-14【算法】326 6 0关键字：阿里云开发者社区在线编程完美排列

完美排列概述：完美排列的定义为一个长度为n的数组，n个元素各不相同且每个元素均在[1,n]的范围内。现在给你长度为n的数组，你每次可以进行如下操作：任选数组中的一个元素，将其加一

示例1
示例2
什么是完美排列？
正确解答

完美排列Xir无知

概述：Xir无知

完美排列的定义为一个长度为n的数组，n个元素各不相同且每个元素均在[1,n]的范围内。
现在给你长度为n的数组，你每次可以进行如下操作：任选数组中的一个元素，将其加一或者减一，问最少需要多少次操作才能够使得该数组为一个完美排列。
输入一个整数n，表示数组的长度(1 <= n <= 10^4)；
再输入含有n个数的数组，第i个数表示数组中的第i个元素为ai（1 <= ai <= 10^5）。
输出一个整数表示将该数组变成一个完美排列的最少操作次数。Xir无知

Xir无知

示例1

输入：
2
[3,0]
输出：
2

注意Xir无知

3->2
0->1
总共需要操作两次Xir无知

示例2

输入：
81
[34,80,53,52,51,65,77,15,28,100,87,65,66,66,49,92,31,8,10,24,84,47,91,63,75,76,76,99,70,99,85,56,28,17,30,64,79,16,54,28,70,26,87,21,31,13,1,11,43,98,98,28,33,23,100,56,36,34,81,36,45,63,71,72,81,53,78,13,63,94,23,67,32,20,18,80,6,18,87,2,91]
输出：
816

什么是完美排列？

完美排列的定义为一个长度为n的数组，n个元素各不相同且每个元素均在[1,n]的范围内。Xir无知

我的理解就是给你3个数，完美排列的结果就是[1,2,3]或者[3,2.1]。Xir无知

正确解答

package solution86;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.util.Arrays;
 
import com.weixiao.roundtable.frame.IOHelper;
 
public class Solution {
    public static int solution(int n, int[] a) {
           int count = 0;
           Arrays.sort(a);//先对数组进行排序，得到升序的数组，例如[1,2,3,4,5]
           //处理第一个元素
           if (a[0] != 1){
                   count = a[0] -1;
                   a[0] = 1;
               }
           for(int i=0;i<a.length-1;i++){
               int d = a[i+1] - a[i];
               if (d > 1){ //比如：a[i+1] =5，a[i] = 3，中间差一个4
                   a[i+1] -= d - 1;
                   count += d - 1;
               }else if (d < 1){
                   a[i+1] += Math.abs(d)+1;
                   count += Math.abs(d)+1;
               }
           }
           return count;
        }
         
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] a = new int[]{34,80,53,52,51,65,77,15,28,100,87,65,66,66,49,92,31,8,10,24,84,47,91,63,75,76,76,99,70,99,85,56,28,17,30,64,79,16,54,28,70,26,87,21,31,13,1,11,43,98,98,28,33,23,100,56,36,34,81,36,45,63,71,72,81,53,78,13,63,94,23,67,32,20,18,80,6,18,87,2,91};
        int count = 0;
        count = solution(81, a);
        System.out.println("count===" + count);
         
        //有时候数组太大，所以只能放到文件中
        BufferedReader br = IOHelper.getBufferedReader("D:/Workspaces_aliyun/test.txt");
        String str = "";
        try {
             str = br.readLine();
        } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
        String[] sa = str.split(",");
        if (sa.length > 0){
            a = new int[sa.length];
            for (int i=0;i<sa.length; i++){
                a[i] = Integer.valueOf(sa[i]);
            }
        }
         
        count = solution(14846, a);
        System.out.println("count===" + count);
         
    }
}