算法1

• 1、开一个数组f[]记录i数字是否出现过

• 2、由于重号只有一个，则输入所有数时，若f[i]为true，则表示该数为重号

• 3、由于断号只有一个，则从最小值minv遍历到最大值maxv，若f[i]为false，则表示该数为断号

时间复杂度 $O(N)$

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int N = 1000010;
    static boolean[] f = new boolean[N];
    static int cid ;
    static int did ;
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine().trim());
        int maxv = Integer.MIN_VALUE;
        int minv = Integer.MAX_VALUE;
        while(n -- > 0)
        {
            String[] s1 = reader.readLine().split(" ");
            for(int i = 0;i < s1.length;i++)
            {
                int t = Integer.parseInt(s1[i]);
                maxv = Math.max(maxv, t);
                minv = Math.min(minv, t);
                if(f[t]) cid = t;
                f[t] = true;
            }
        }
        for(int i = minv ;i <= maxv ;i ++)
        {
            if(!f[i])
            {
                did = i;
                break;
            }
        }
        System.out.println(did + " " + cid);
    }

}

算法2

• 1、通过对输入的编号进行排序

• 2、从小到大遍历
  （1）由于重号只会出现一个，因此当a[i] == a[i - 1]时，a[i]表示重号
  （2）由于断号只会出现一个，因此一定会空缺一个数，则当a[i] == a[i - 1] + 2时，a[i] - 1表示断号

时间复杂度 O(klogk)

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int[] a = new int[100010];
    static int k = 0;
    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine().trim());
        while(n -- > 0)
        {
            String[] s1 = reader.readLine().split("\\s+");
            for(int i = 0;i < s1.length;i++)
            {
                a[k ++] = Integer.parseInt(s1[i]);
            }
        }
        Arrays.sort(a,0,k);
        int res1 = -1;//断号(只会断一次)
        int res2 = -1;//重号
        for(int i = 1;i < k;i++)
        {
            if(a[i] == a[i - 1]) res2 = a[i];//重号
            else if(a[i] == a[i - 1] + 2) res1 = a[i] - 1;//断号
        }
        System.out.println(res1 + " " + res2);
    }
}