正则序列

[编程题]正则序列

热度指数：20537 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

输出

算法知识视频讲解

Java

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)

Java

kkkkkkk1771

无需排序，需要数学思维思考一下，把所有的负数变成从 1~（负数个数）所有正数变为（负数个数+1）~n;

时间复杂度 O（N）

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        scan.nextLine();
        String[] arr = scan.nextLine().split(" ");
        int[] scores = new int[n];
        for(int i = 0;i<n;i++){
            scores[i]=Integer.parseInt(arr[i]);
        }
         int neg = 0;
        int negNum = 0;
        int pos = 0;
        int posNum = 0;
        for(int i = 0;i<n;i++){
            if(scores[i]<0){
                neg+=scores[i];
                negNum++;
            }else{
                pos+=scores[i];
                posNum++;
            }
        }
        int negSum = negNum>0 ?negNum*(negNum+1)/2 - neg : 0;
        int posSum = posNum>0?   Math.abs((posNum)*(2*n-posNum+1)/2 - pos) : 0;
        int sum  = negSum+ posSum;

        System.out.println(sum);
        
        
    }
}

编辑于 2022-04-08 21:27:21 回复(1)