算法您现在的位置是:首页 > 博客日志 > 算法

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

<a href='mailto:'>微wx笑</a>的头像微wx笑2020-07-14 21:30:19算法人已围观关键字: 阿里云  开发者社区  在线编程  完美排列  

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

完美排列qzA编程技术_踩坑日志_进阶指南_无知人生

概述:qzA编程技术_踩坑日志_进阶指南_无知人生

完美排列的定义为一个长度为n的数组,n个元素各不相同且每个元素均在[1,n]的范围内。
现在给你长度为n的数组,你每次可以进行如下操作:任选数组中的一个元素,将其加一或者减一,问最少需要多少次操作才能够使得该数组为一个完美排列。
输入一个整数n,表示数组的长度(1 <= n <= 10^4);
再输入含有n个数的数组,第i个数表示数组中的第i个元素为ai(1 <= ai <= 10^5)。
输出一个整数表示将该数组变成一个完美排列的最少操作次数。qzA编程技术_踩坑日志_进阶指南_无知人生


qzA编程技术_踩坑日志_进阶指南_无知人生

示例1

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

注意qzA编程技术_踩坑日志_进阶指南_无知人生

3->2
0->1
总共需要操作两次qzA编程技术_踩坑日志_进阶指南_无知人生

示例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]的范围内。qzA编程技术_踩坑日志_进阶指南_无知人生

我的理解就是给你3个数,完美排列的结果就是[1,2,3]或者[3,2.1]。qzA编程技术_踩坑日志_进阶指南_无知人生

正确解答

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);
    	
	}
}


qzA编程技术_踩坑日志_进阶指南_无知人生


qzA编程技术_踩坑日志_进阶指南_无知人生


qzA编程技术_踩坑日志_进阶指南_无知人生


qzA编程技术_踩坑日志_进阶指南_无知人生

本文由 微wx笑 创作,采用 CC BY-NC 4.0 许可协议。 非商业性使用可自由转载、引用、甚至修改,但需署名作者且注明出处。

很赞哦! () 有话说 ()