首页 > 试题广场 >

正则序列

[编程题]正则序列

我们称一个长度为n的序列为正则序列，当且仅当该序列是一个由1~n组成的排列，即该序列由n个正整数组成，取值在[1,n]范围，且不存在重复的数，同时正则序列不要求排序

有一天小团得到了一个长度为n的任意序列s，他需要在有限次操作内，将这个序列变成一个正则序列，每次操作他可以任选序列中的一个数字，并将该数字加一或者减一。

请问他最少用多少次操作可以把这个序列变成正则序列？

数据范围： $1\le n \le 20000\$ ， $0\le abs(s_i) \le 10000 \$

进阶：时间复杂度 $O(n)\$ ，空间复杂度 $O(n)\$

输入第一行仅包含一个正整数n，表示任意序列的长度。(1<=n<=20000)
输入第二行包含n个整数，表示给出的序列，每个数的绝对值都小于10000。

输出仅包含一个整数，表示最少的操作数量。

示例1

输入

5
-1 2 3 10 100

算法知识视频讲解

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

C++工程师 iOS工程师安卓工程师美团前端工程师算法工程师 2021 大数据开发工程师 Java工程师

上传者：小小

难度：

0条回答 284收藏 15474浏览

扫一扫，把题目装进口袋