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

完美排列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);
    	
	}
}

Xir无知

Xir无知

Xir无知

Xir无知

本文由 微wx笑 创作，采用 署名-非商业性使用-相同方式共享 4.0 许可协议，转载请附上原文出处链接及本声明。
原文链接：https://www.ivu4e.cn/blog/algorithm/2020-07-14/507.html

很赞哦！ () 赏 有话说 ()