题解 | 数独数组

频率分布一致性判定 (Frequency Consistency)

逻辑原理：

1. 周期性要求：正如上述分析，一个合格的数独数组必须满足 a_i = a_i+9。这意味着数字 1 在数组中出现的次数、数字 2 出现的次数...直到数字 9 出现的次数，必须非常“均匀”。
2. 数学推导： 设 n = 9k + r，其中 0 <= r <= 9。这意味着有 r 个位置会出现 k+1 次，剩下的 9-r 个位置会出现 k 次。结论：只要统计输入数组中 1 ~ 9 每个数字出现的频率，将这些频率排序。如果排序后的频率数组恰好有 r 个值等于 k+1，且有 9-r 个值等于 k，那么一定可以构造出数独数组。

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] counts = new int[10]; // 统计 1-9 出现的次数
        for(int i = 0; i < n; i++) {
            int val = in.nextInt();
            counts[val]++;
        }

        // 提取 1-9 的频率并排序
        int[] freq = new int[9];
        for(int i = 1; i <= 9; i++) {
            freq[i - 1] = counts[i];
        }
        Arrays.sort(freq);

        // 计算理论上的频率分布
        int k = n / 9;
        int r = n % 9;

        // 预期的频率应该是：9-r 个 k，和 r 个 k+1
        boolean possible = true;
        for(int i = 0; i < 9 - r; i++) {
            if(freq[i] != k) possible = false;
        }
        for(int i = 9 - r; i < 9; i++) {
            if(freq[i] != k + 1) possible = false;
        }

        System.out.println(possible ? "YES" : "NO");
    }
}