直接暴力求解

被卡在7/11

import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = Integer.parseInt(sc.nextLine());
        String[] s = sc.nextLine().split(" ");
        int[] a = new int[n + 1];
        for (int i = 1; i <= n; i++) a[i] = Integer.parseInt(s[i - 1]);

        HashSet<Integer> set = new HashSet<>();

        set.add(a[1]);
        for (int i = 2; i <= n; i++) {
            int t = a[i];
            while (set.contains(t)) t++;
            a[i] = t;
            set.add(t);            
        }
        for (int i = 1; i <= n; i++)
            System.out.print(a[i] + " ");
    }
}

优化读入输出

7/11

import java.util.*;
import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);

        int n = Integer.parseInt(sc.readLine());
        String[] s = sc.readLine().split(" ");
        int[] a = new int[n + 1];
        for (int i = 1; i <= n; i++) a[i] = Integer.parseInt(s[i - 1]);

        HashSet<Integer> set = new HashSet<>();

        set.add(a[1]);
        for (int i = 2; i <= n; i++) {
            int t = a[i];
            while (set.contains(t)) t++;
            a[i] = t;
            set.add(t);            
        }
        for (int i = 1; i <= n; i++)
            out.print(a[i] + " ");

        out.flush();
    }
}

自己实现hash

7/11

import java.util.*;
import java.io.*;

public class Main {
    static final int N = 2000010;
    static int[] hash = new int[N];

    public static void main(String[] args) throws IOException {

        BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);

        int n = Integer.parseInt(sc.readLine());
        String[] s = sc.readLine().split(" ");
        int[] a = new int[n + 1];
        for (int i = 1; i <= n; i++) a[i] = Integer.parseInt(s[i - 1]);

        hash[a[1]] = 1;
        for (int i = 2; i <= n; i++) {
            int t = a[i];
            while (hash[t] != 0) t++;
            a[i] = t;
            hash[t] = 1;            
        }

        for (int i = 1; i <= n; i++)
            out.print(a[i] + " ");

        out.flush();
    }
}

考虑每次都修改比较慢，改成判断

卡在10/11(到最坏情况了每个元素都相同(n*n)的时间复杂度)

import java.util.*;
import java.io.*;

public class Main {
    static final int N = 2000010;
    static int[] hash = new int[N];

    public static void main(String[] args) throws IOException {

        BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);

        int n = Integer.parseInt(sc.readLine());
        String[] s = sc.readLine().split(" ");
        int[] a = new int[n + 1];
        for (int i = 1; i <= n; i++) a[i] = Integer.parseInt(s[i - 1]);

        hash[a[1]] = 1;
        for (int i = 2; i <= n; i++) {
            int t = a[i], flag = 1;
            while (hash[t] != 0) {
                t++;
                flag = 0;
            }
            if (flag == 0) a[i] = t;
            hash[t] = 1;
        }

        for (int i = 1; i <= n; i++)
            out.print(a[i] + " ");

        out.flush();
    }
}

并查集

import java.util.*;
import java.io.*;

public class Main {
    static final int N = 1100010;
    static int[] p = new int[N];

    public static void main(String[] args) throws IOException {

        BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);

        for (int i = 1; i < N; i++) p[i] = i;
        int n = Integer.parseInt(sc.readLine());
        String[] s = sc.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            int x = Integer.parseInt(s[i]);

            x = find(x);
            out.print(x + " ");
            p[x] = x + 1;
        }

        out.flush();
    }

    static int find(int x) {
        if (x != p[x]) p[x] = find(p[x]);
        return p[x];
    }
}