题解 | mex-Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        long[] a = new long[n]; 
        
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextLong();
        }
        
        System.out.println(minOperations(a, n));
        scanner.close();
    }
    
    private static Long minOperations(long[] a, int n) {
        // 情况1：如果数组中所有元素已经相同，返回0
        if (allElementsSame(a, n)) {
            return 0L;
        }
        
        // 检查数组中是否包含0
        boolean hasZero = false;
        for (long num : a) {
            if (num == 0) {
                hasZero = true;
                break;
            }
        }
        
        // 情况2：如果数组元素不相同且不包含0，则不可能完成，返回-1
        if (!hasZero) {
            return -1L;
        }
        
        // 收集所有正整数并去重
        Set<Long> positiveNumbers = new HashSet<>();
        for (long num : a) {
            if (num > 0) {
                positiveNumbers.add(num);
            }
        }
        
        // 将去重后的正整数转换为列表并排序
        List<Long> positives = new ArrayList<>(positiveNumbers);
        Collections.sort(positives);
        
        // 正整数的个数使用int类型
        int m = positiveNumbers.size();
        // 最大的正整数
        long maxP = positives.get(m - 1);
        
        // 应用公式计算结果：maxP - (m - 1)
        return maxP - (m - 1);
    }
    
    // 检查数组是否所有元素都相同
    private static boolean allElementsSame(long[] a, int n) {
        if (n <= 1) {
            return true;  // 空数组或只有1个元素，自然所有元素相同
        }
        
        long first = a[0];  // 以第一个元素为基准
        for (int i = 1; i < n; i++) { 
            if (a[i] != first) {  // 只要有一个元素与基准不同，就返回false
                return false;
            }
        }
        return true;  // 所有元素都与基准相同，返回true
    }
}