首页 > 试题广场 >

正则序列

[编程题]正则序列
  • 热度指数：20469 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解

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

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

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

数据范围：，
进阶：时间复杂度，空间复杂度

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


输出描述:
输出仅包含一个整数，表示最少的操作数量。
示例1

输入

5
-1 2 3 10 100

输出

103
算法知识视频讲解
添加回答
pein531头像 pein531
先对输入的序列进行升序排列。我们需要明白，无论是什么排列的正则序列，改动最少的方案一定是对输入序列和正则序列中相同排名的元素进行修改，即输入序列中排名第 i 的元素应该修改为正则序列中的 i。除此之外，其他的任何方案都至少存在一个数，使得它并不是修改为离它最近的正则序列中的数，这样就会使得修改次数增多。 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        String[] strSeq = br.readLine().trim().split(" ");
        int[] seq = new int[n];
        for(int i = 0; i < n; i++) seq[i] = Integer.parseInt(strSeq[i]);
        Arrays.sort(seq);
        int modifyTimes = 0;
        for(int i = 1; i <= n; i++) modifyTimes += Math.abs(seq[i - 1] - i);
        System.out.println(modifyTimes);
    }
}


发表于 2021-03-07 17:44:54 回复(13)
chenjc23头像 chenjc23
n = int(input())
li = [int(i) for i in input().split()]
li.sort()
result = 0
for i in range(n):
    result += abs(i+1-li[i])
print(result)
发表于 2021-03-02 00:09:11 回复(1)
牛客585309717号头像 牛客585309717号 
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdlib.h>


using namespace std;

int main() {
	int n, ans = 0;;
	cin >> n;
	vector<int>que(n, 0);
	for (int i = 0; i < n; ++i) cin >> que[i];
	sort(que.begin(), que.end());
	for (int i = 1; i <= n; ++i) {
		ans += abs(i - que[i - 1]);
	}
	cout << ans;
	return 0;
}
排序修改步数最少这一点，画个图拿两个点举例就会发现这充其量是初中证明题。
能用STL就坚决不自己写。
发表于 2021-08-11 20:29:15 回复(2)
七层楼头像 七层楼

刚开始没看出来这道题目考的是什么？其实就是贪心。我们要让每个数字移动的步数最少，或者说让每个数字找距离下标[1,n]最近的位置填充。当时思路是有了，但是我一直没有排序，所以测试样例通过了，然后整体运行通不过，百思不得解。后来发现先排序，然后将所有数字按照[1,n]的坑位从小到大填。这样就能保证距离最小，整体思路是对的，还要保证数组整体有序。
保证最后所有的数值取值在[1,n]，先排序，然后从左到右遍历，这样就能取得最小步数。

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr);
        int res = 0;
        for(int j=1;j<=n;j++){
            res += Math.abs(arr[j-1] - j);
        }
        System.out.println(res);
    }
}

以上，下课

发表于 2021-08-14 16:52:56 回复(2)
小橘子🍊201812261626381头像 小橘子🍊201812261626381 
n = int(input())
a = list(map(int, input().strip().split()))
a.sort()
sum = 0
for i in range(1,n+1):
    sum += abs(i-a[i-1])
print(sum)

发表于 2021-03-17 21:22:52 回复(0)
Skyed__blue头像 Skyed__blue
其实就是贪心。我们要让每个数字移动的步数最少，或者说让每个数字找[1,n]最近的坑位填。
我们可以先排序，然后将所有数字按照`[1,n]`的坑位从小到大填。

以下是临场笔记思路...

```cpp
//取值在[1,n]
//先排序，然后从左到右遍历
//让每个数都走到缺省的值
 
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    int n;
    int arr[20020];
    scanf("%d",&n);
    for(int i = 0;i < n;i++)
    {
        scanf("%d",&arr[i]);
    }
    sort(arr,arr+n);
    int k = 1;
    int ans = 0;
    for(int i = 0;i < n;i++)
    {
        ans += abs(k-arr[i]);
        k++;
    }
    cout<<ans<<endl;
}
```
发表于 2021-03-15 20:36:58 回复(0)
不投降头像 不投降 
import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        int ans = 0;
        for(int i = 0;i < n;i++)
            nums[i] = sc.nextInt();
        Arrays.sort(nums);
        for(int i = 0;i < n;i++){
            ans += Math.abs(i + 1 - nums[i]);
        }
        System.out.println(ans);
    }
}

发表于 2022-03-30 19:43:35 回复(0)
Ak_Wu头像 Ak_Wu
标准答案在这：

为了满足题目的时间复杂度要求，显然我们需要进行数组的排序，但是明显直接sort复杂度是O(n)的，不过可以庆幸的是每个数的范围都不大，而O(n)的排序就只有桶排序了，所以本体排序直接用桶排序即可满足复杂度要求。

不过需要注意的是，数是可能为负数的，我们桶排序开的数组下表不能出现负数，所以需要将对每个转为正数后再桶排序，最后求的时候不要忘记转回来！！！ 
#include<iostream>
using namespace std;

const int N = 2e4 + 5;
int n;
int a[N], tmp[N];

int main()
{
    cin >> n;
    
    int _max = 0;
    for (int i = 1; i <= n; i ++ ) {
        cin >> a[i];
        tmp[a[i] + 10000]++;
        _max = max(_max, a[i] + 10000);
    }
    
    int idx = 0;
    for (int i = 0; i <= _max; i ++ ) {
        if (!tmp[i]) {
            continue;
        }
        while (tmp[i] -- > 0) {
            a[idx ++ ] = i - 10000;
        }
    }
    
    int ans = 0;
    for (int i = 1; i <= n; i ++ ) {
        ans += abs(i - a[i - 1]);
    }
    
    cout << ans << endl;
    
    return 0;
}
发表于 2022-02-16 21:52:26 回复(7)
kjldvsdhv头像 kjldvsdhv 
n = int(input())
nums = list(map(int, input().split()))
total = 0
 
nums.sort()
 
for i in range(n):
    total += abs(i + 1 - nums[i])
     
print(total)

编辑于 2022-01-18 16:17:25 回复(1)
McQueen头像 McQueen
先排序，然后将数字在[1, n]内的元素原地哈希一下，放到对应的位置，则这些对应的元素就不用做操作。然后从头到尾遍历，遇到元素的值不等于下标的，那么当前元素的操作次数就是元素值与下标的差的绝对值 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> nums(n);
    for(int i = 0; i < n; i++)
        cin >> nums[i];
    int count = 0;
    sort(nums.begin(), nums.end());
    for(int i = 0; i < n; i++)
    {
        if(nums[i] >= 1 && nums[i] <= n)
            swap(nums[i], nums[nums[i] - 1]);
    }
    for(int i = 1; i <= n; i++)
    {
        if(i != nums[i - 1])
            count += abs(nums[i - 1] - i);
    }
    cout << count << endl;
    return 0;
}


发表于 2021-04-04 15:04:01 回复(0)
牛客538262668号头像 牛客538262668号 
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        int minCount = new Main().minCount();
        System.out.println(minCount);
    }

    public int minCount(){
        Scanner scanner = new Scanner(System.in);
        int n=scanner.nextInt();
        int[] arr=new int[n];
        for(int i=0;i<n;i++)
            arr[i]=scanner.nextInt();

        Arrays.sort(arr);
        int res=0;

        for(int i=0;i<n;i++){
            res+=Math.abs(arr[i]-(i+1));
        }

        return res;
    }
}

发表于 2021-02-27 16:19:19 回复(0)
糖同学头像 糖同学 
input()
nums=[int(x) for x in input().split()]
nums.sort()
n=len(nums)
ans=0
for i in range(n):
    ans+=abs(nums[i]-(i+1))
print(ans)


编辑于 2021-02-25 13:32:10 回复(0)
C/C++
牛客207191353号头像 牛客207191353号 
#include<iostream>
using namespace std;
int main(){
    int n;
    cin >> n;
    int b[20001] = {0};
    for (int i = 0, num; i < n; i++) {
        cin >> num;
        b[num + 10000]++;
    }
    int ans = 0;
    for (int num = 0, j = 1; num < 20001 && j <= n; num++) {
        while (b[num]--) {
            ans += abs(j++ - num + 10000);
        }
    }
    cout << ans;
    return 0;
}
编辑于 2022-08-29 22:22:12 回复(0)
牛客304000217号头像 牛客304000217号
我的办法比较保守，就是把随意序列不符合正则的，比如超过范围或者重复元素的放进一个切片中more，把随意里面没有正则元素的放进另一个切片less，结束后两个切片都是升序排列，然后长度相等，循环相减累加和就是结果。 
package main
import (
	"fmt"
	"sort"
)
func S(nums []int)int{
	sort.Ints(nums)
	res:=0
	n:=len(nums)
	var less,more []int
	myMap:=make(map[int]int,n)
	for i:=0;i<n;i++ {  //把随意序列存进map并记录有多少个重复
		myMap[nums[i]] += 1
	}
		for i:=1;i<=len(nums);i++{ //循环正则序列的值，与随意序列比较有无多或少元素，多存进more，少存进less

			v,ok:=myMap[i]
			if nums[i-1]<1||nums[i-1]>=n+1{ //注意把超过n范围的元素加入more
				more=append(more,nums[i-1])
			}
			if ok{
				if v>1{
					add(&more,v-1,i)
					continue
				}
				continue
			}

			less=append(less,i)
		}

	for i:=len(more)-1;i>=0;i--{ //此时more和less已经排序浩，长度相等，逐个相减累加和，就是结果
		if more[i]>less[i]{
			res+=more[i]-less[i]
		}else{
			res+=less[i]-more[i]
		}
	}
	return res
}



func add(a *[]int, b,c int){
	for i:=1;i<=b;i++{
		*a=append(*a,c)
	}
}
func main(){
	var n int
	fmt.Scan(&n)
	nums:=make([]int,n)

	for i:=0;i<n;i++{
		fmt.Scan(&nums[i])
	}
	res:=S(nums)
	fmt.Println(res)
}


发表于 2022-05-19 20:06:10 回复(0)
苦逼的90后头像 苦逼的90后
***乱写 
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] arr1=new int[n];
        int[] arr2=new int[n];
        for (int i = 0; i < n; i++) {
            arr1[i]=i+1;
            arr2[i]=sc.nextInt();
        }
        Arrays.sort(arr2);
        int sum=0;
        for (int i = 0; i < n; i++) {
            arr1[i]=Math.abs(arr1[i]-arr2[i]);
            sum+=arr1[i];
        }
        System.out.println(sum);
    }
}


发表于 2021-05-29 16:56:24 回复(0)
牛客822514231号头像 牛客822514231号
简单暴力 
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int[] arr = new int[n];
        int res = 0;
        for(int i = 0;i<n;i++){
            arr[i] = s.nextInt();
        }
        Arrays.sort(arr);
        while(arr[0] < 1){
            arr[0]++;
            res++;
        }
        for(int i = 1;i<n;i++){
            while(arr[i] <= arr[i-1]){
                arr[i]++;
                res++;
            }
        }
        System.out.println(res);
    }
}


发表于 2021-03-08 16:36:40 回复(2)
牛客299976043号头像 牛客299976043号
不知道这样对不对，用的哈希 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    int t = 0;
    int count = 0;
    vector<int> hash(n + 1,0);
    for (int i = 0; i < n; i++) {
        cin >> t;
        if (t >= 1 && t <= n) {
            hash[t]++;
        }
        else if (t < 1) {
            count = count + 1 - t;
            hash[1]++;
        }
        else if (t > n) {
            count = count + t - n;
            hash[n]++;
        }
 
    }
    int sum = 0;
    for(int i=1;i<=n;i++) {
        sum = sum + hash[i] * i;
    }
    count = count + (1+n)*n/2 - sum;
 
    cout << count ;
}


编辑于 2024-03-15 23:34:54 回复(0)
Java
Errerless头像 Errerless
将输入都映射到 1-n，从小到大双指针遍历，遇到出现次数大于 1 的数字则需要改动若干次，填补出现次数为 0 的数字，时空复杂度均为 O(n) 
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int ans = 0;
        int[] a = new int[n + 1];
        for (int i = 0; i < n; i++) {
            int k = in.nextInt();
            if (k < 1) {
                ans += 1 - k;
                a[1]++;
            } else if (k > n) {
                ans += k - n;
                a[n]++;
            } else {
                a[k]++;
            }
        }
        int x = 1;
        for (int i = 0; i <= n; i++) {
            while (a[i] > 1) {
                while (a[x] != 0) x++;
                ans += Math.abs(i - x);
                a[i]--;
                a[x]++;
            }
        }
        System.out.println(ans);
    }
}


编辑于 2024-03-01 13:18:49 回复(0)
GolinYoung头像 GolinYoung
需要注意：该序列由n个正整数组成，取值在[1,n]范围；
代表着n个数的正则序列必须是1,2，...，n；由此才能想到输入序列中排名第 i 的元素应该为i；

发表于 2023-09-14 21:30:11 回复(0)
Lysen-Goto头像 Lysen-Goto
时间复杂度为 O(N) 的解法：用桶排序 
import java.util.Scanner; 
import java.lang.Math;

// 贪心算法：对序列 s 进行排序，第 i 位通过加减乘除变成 i
// 优化：采用桶排序
public class Main {
    public static void main(String[] args) {
        // value 映射到 value+10000 上
        int[] buckets = new int[20001];
        // 输入数组，放入桶中
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        while (n-- > 0) {
            ++buckets[scanner.nextInt()+10000];
        }
        // 第 i 位通过加减乘除变成 i
        int result = 0, i = 1;
        for (int j = 0; j <= 20000; ++j) {
            while (buckets[j]-- > 0) {
                result += Math.abs((j-10000) - (i++));
            }
        }
        System.out.println(result);
    }
}


发表于 2023-07-17 12:20:11 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 美团 前端工程师 算法工程师 2021 大数据开发工程师 Java工程师
上传者：小小
难度：
81条回答 15448浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号