首页 > 试题广场 >

正则序列

[编程题]正则序列

我们称一个长度为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

算法知识视频讲解

牛客207191353号

发表于 2022-08-29 18:43:53

#include<iostream> using namespace std; int main(){ int n; cin >> n; int b[20001] = {0}; for (int i = 0, num; i < n; i+ 展开全文

大厂算法岗必拿下

发表于 2021-09-22 07:32:16

注意读题 #include<bits/stdc++.h> using namespace std; int main(){ int n,x; vector<int> p; while(cin>>n){ p.clear(); 展开全文

牛客279909514号

发表于 2022-09-02 18:03:45

有限自动机解法,O(N)复杂度，伪动态规划具体思路如下：首先对于超出边界的(小于等于0，大于n)，可以直接归到边界。记录每个数字出现的个数，采用有限状态机一次遍历可以得到答案分为三个状态：初始状态，多余状态和缺少状态。设当前遍历为index，多余状态多余的数均为index-1；缺少状态缺少展开全文

小牛冲冲冲jiang

发表于 2021-09-22 04:50:18

import java.util.Scanner; import java.util.*; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(Sy 展开全文

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

上传者：小小

难度：

81条回答 285收藏 16061浏览