当前位置：首页 > article >正文

牛客周赛77B：JAVA

article 2025/2/28 19:40:37

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网

题目描述

\hspace{15pt}对于给定的由 nnn 个整数组成的数组 {a1,a2,…,an}\{a_1, a_2, \dots, a_n\}{a1,a2,…,an}，我们称其为数独数组，当且仅当其每一个长度为 999 的连续子数组，都包含 1∼91 \sim 91∼9 这 999 个数字。
\hspace{15pt}现在，对于给定的数组，是否存在一种方案，使得其经过重新排序后成为数独数组？如果是，直接输出 YES\rm YESYES；否则，输出 NO\rm NONO。注意，您不必给出具体的排序方案。

输入描述:

\hspace{15pt}第一行输入一个整数 n(9≦n≦105)n \left(9 \leqq n \leqq 10^5\right)n(9≦n≦105) 代表数组中的元素数量。
\hspace{15pt}第二行输入 nnn 个整数 a1,a2,…,an(1≦ai≦9)a_1, a_2, \dots, a_n \left(1 \leqq a_i \leqq 9\right)a1,a2,…,an(1≦ai≦9) 代表数组元素。

输出描述:

\hspace{15pt}如果数组在重新排序后可以成为数独数组，输出 YES\rm YESYES；否则，输出 NO\rm NONO。

示例1

输入

9
1 2 3 4 5 6 7 9 8

输出

YES

说明

\hspace{15pt}在这个样例中，不需要经过重新排序，数组已经是一个数独数组。

示例2

输入

9
1 2 3 4 5 6 7 8 1

输出

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 创建一个Scanner对象用于读取输入
        Scanner sc = new Scanner(System.in);
        
        // 读取整数n，表示接下来有n个数字需要处理
        int n = sc.nextInt();
        
        // 创建一个长度为10的数组count，用于记录每个数字（0-9）的出现次数
        int[] count = new int[10];
        
        // 循环读取n个数字，并统计每个数字出现的次数
        for (int i = 0; i < n; i++) {
            int num = sc.nextInt(); // 读取一个数字
            count[num]++; // 对应位置的计数器加1
        }
        
        // 检查任意两个不同数字的出现次数之差是否大于1
        for(int i = 1; i <= 9; i++){
            for(int j = i + 1; j <= 9; j++){
                // 如果两个数字的出现次数之差大于1，则输出"NO"并结束程序
                if(Math.abs(count[i] - count[j]) > 1){
                    System.out.println("NO");
                    return ;
                }
            }
        }
        
        // 如果所有数字的出现次数之差都小于等于1，则输出"YES"
        System.out.println("YES");
    }
}