首页 > 试题广场 >

数独数组

[编程题]数独数组
  • 热度指数：9103 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 1024M，其他语言2048M
  • 算法知识视频讲解
\hspace{15pt}对于给定的由 n 个整数组成的数组 \{a_1, a_2, \dots, a_n\}，我们称其为数独数组，当且仅当其每一个长度为 9 的连续子数组，都包含 1 \sim 9 这 9 个数字。
\hspace{15pt}现在，对于给定的数组，是否存在一种方案，使得其经过重新排序后成为数独数组？如果是，直接输出 \rm YES；否则，输出 \rm NO。注意，您不必给出具体的排序方案。

输入描述:
\hspace{15pt}第一行输入一个整数 n \left(9 \leqq n \leqq 10^5\right) 代表数组中的元素数量。
\hspace{15pt}第二行输入 n 个整数 a_1, a_2, \dots, a_n \left(1 \leqq a_i \leqq 9\right) 代表数组元素。


输出描述:
\hspace{15pt}如果数组在重新排序后可以成为数独数组，输出 \rm YES；否则，输出 \rm NO。
示例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

输出

NO
算法知识视频讲解
添加回答
Python3
_en头像 _en
import sys

# 接收数据
data = []
for line in sys.stdin:
    a = list(map(int, line.rstrip().split()))
    data.append(a)

# 统计字符串中各数字个数
dic = {1:0, 2:0, 3:0, 4:0, 5:0, 6:0, 7:0, 8:0, 9:0}
for i in data[1]:
    dic[i] += 1

# 对各数字出现次数进行排序
dic2 = sorted(dic.items(), key=lambda x:x[1])

# 1-9都出现，且出现次数差值最大不超过1，则可构成数独数组
# 数组长度不为9的倍数也可，eg:2 3 4 1 5 6 7 8 9 2 3 4
if list(dic2)[0][1] != 0 and list(dic2)[-1][1] - list(dic2)[0][1] <= 1:
    print("YES")
else:
    print("NO")

发表于 2025-03-24 14:40:59 回复(0)
Java
牛客430757235号头像 牛客430757235号
/*以下是我第一次考虑想到的代码 主要逻辑 统计1-9数字出现的次数 使用HashMap 存储并记录  得到某个数字出现次数最小值min 要满足min大于等于全部元素个数除以9 （取整）  此时输出YES 否则输出NO    
在17/18用例卡住 一直想不通是为什么  问了问D老师  并没有解决 看了看其他网友的C++答案  豁然开朗  我少考虑了一种情况 即某个数字超级多！！！ 比如输入14个数字 1 2 3 4 5 6 7 8 9 9 9 9 9 9 如果按原来代码 此时会输出YES  但正确答案是NO 因为太多9了 这些9没法构成连续1-9 这就是原因！！
*/
import java.util.Scanner;
import java.util.Map;
import java.util.HashMap;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int a = in.nextInt();//a/9
        in.nextLine();
        String[] b = in.nextLine().split("\\s+");
        StringBuilder c = new StringBuilder();
        for(String i:b){
            c.append(i);
        }
        String d = c.toString();

        Map<Character, Integer> w = new HashMap<>();
        for(int i = 1;i<10;i++){
            w.put(Character.forDigit(i,10),0);
        }
        for (int i = 0; i < a; i++) {
            w.put(d.charAt(i),w.getOrDefault(d.charAt(i),0)+1);
        }//计每个数字出现次数
        int min = Integer.MAX_VALUE;
        for (Map.Entry<Character, Integer> e : w.entrySet()) {
            min = Math.min(min, e.getValue());
        }
        if (min >= (a / 9)) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
}
/*修改代码如下 这下可以了 谢谢C++网友 经过仔细分析考虑 当数字出现的最大值max 与最小值min 如果(max-min) >1的话 此时也是输出NO  举例子
原始数据 19个数字 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 5  可以 排序为 5123467895123467895  此时每连续9个数字都可以达到数独数组  其他数字出现都是2次 5出现了3次
原始数据 20个数字 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 5 5 怎么排都不可以 例如排序为 5123467895123467895 还有一个5 没有地方了（放进去会导致存在至少一组数组不满足数独数组) 此时其他数字出现都是2次 5出现了4次  4-2为2 大于1 输出NO！！
修改代码如下
*/
import java.util.Scanner;
import java.util.Map;
import java.util.HashMap;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int a = in.nextInt();//a/9
        in.nextLine();
        String[] b = in.nextLine().split("\\s+");
        StringBuilder c = new StringBuilder();
        for (String i : b) {
            c.append(i);
        }
        String d = c.toString();

        Map<Character, Integer> w = new HashMap<>();
        for (int i = 1; i < 10; i++) {
            w.put(Character.forDigit(i, 10), 0);
        }
        for (int i = 0; i < a; i++) {
            w.put(d.charAt(i), w.getOrDefault(d.charAt(i), 0) + 1);
        }//计每个数字出现次数
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (Map.Entry<Character, Integer> e : w.entrySet()) {
            min = Math.min(min, e.getValue());
            max = Math.max(max, e.getValue());
        }
        if ((max - min) > 1) {//这里多进行一次判断 出现次数最大值减去出现次数最小值 >1就输出NO！！
            System.out.println("NO");
        } else {
            if (min >= (a / 9)) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }

    }
}


发表于 2025-03-16 20:53:48 回复(0)
Java
牛客281381469号头像 牛客281381469号 
定义一个容量为10的数组来存储数字1~9，接收控制台过来的每个数字。
如1，则把map[1] += 1，若排序能形成结果，每个数字的数量满足  >= n / 9且<= n / 9 + 1。
如果不满足，则输出NO。若满足，则输出YES
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int numberCount = in.nextInt();
            int[] map = new int[10];
            for (int i = 0; i < numberCount; i++) {
                map[in.nextInt()]++;
            }
            String res = "YES";
            for (int i = 1; i <= 9; i++) {
                if (map[i] >= numberCount / 9 && map[i] <= numberCount / 9 + 1) {
                    continue;
                } else {
                    res = "NO";
                    break;
                }
            }
            System.out.println(res);
        }
    }
}

发表于 2025-07-19 16:17:10 回复(2)
Python3
theyoungestontop头像 theyoungestontop 
n = int(input())
an = list(map(int, input().strip().split(' ')))
if not (9<=n<=10**5 and len(an) == n and all(1<=ai<=9 for ai in an)):
    print('请输入有效范围内的整数n和数组元素ai')
else:
    dic = {}
    for ai in an:
        dic[ai] = dic.get(ai, 0) + 1
    if len(set(dic.keys())) == 9 and (max(dic.values()) - min(dic.values())) <= 1:
        print('YES')
    else:
        print('NO')
# 构成数独数组的关键是1-9这9个数字都得至少出现一次，并且各个数字出现次数的最大值与最小值之间不超过1。
# 是否构成数独数组与数组长度是否为9的倍数无关。【1，2，3，4，5，6，7，8，9，1，2，3】仍是数独数组。
# 【1，2，3，4，5，6，7，7，9】不是数独数组。【1，2，3，4，5，6，7，7，7，8，9】不是数独数组。

发表于 2025-06-10 17:19:03 回复(0)
C
乐观的马后炮炮手在敲键盘头像 乐观的马后炮炮手在敲键盘
#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
   
    int cnt[10] = {0}; // 统计每个数字出现次数，cnt[1]到cnt[9]
   
    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        cnt[x]++;
    }
   
    int k = n / 9;      // 每个数字至少出现k次
    int r = n % 9;      // 有r个数字需要多出现一次
   
    // 检查：必须有r个数字出现k+1次，9-r个数字出现k次
    int needKplus1 = 0;  // 需要出现k+1次的数字个数
    int needK = 0;       // 需要出现k次的数字个数
   
    for (int i = 1; i <= 9; i++) {
        if (cnt[i] == k + 1) {
            needKplus1++;
        } else if (cnt[i] == k) {
            needK++;
        } else {
            // 出现次数既不是k也不是k+1，不可能
            printf("NO\n");
            return 0;
        }
    }
   
    // 需要r个数字出现k+1次，9-r个数字出现k次
    if (needKplus1 == r && needK == 9 - r) {
        printf("YES\n");
    } else {
        printf("NO\n");
    }
   
    return 0;
}
发表于 2026-04-20 11:48:44 回复(0)
猫猫猫1头像 猫猫猫1 
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    while (cin >> n) {
        vector<int> v(10, 0);
        int num;
        for (int i = 0; i < n; i++) {
            cin >> num;
            v[num]++;
        }
        int Min = *min_element(v.begin() + 1, v.end());
        int Max = *max_element(v.begin() + 1, v.end());
        if (Max - Min <= 1) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    return 0;
}

发表于 2026-04-16 19:47:38 回复(0)
C++
马里奥离上岸不远了头像 马里奥离上岸不远了
有的同学会卡17/18,这时就要判断  n%9 !=0 时 多出输入的数的个数  需要  == n%9 
#include <bits/stdc++.h>
using namespace std;
using ll=long long;

int main() 
{
    int n;
    cin>>n;
    vector<int> a(n),cnt(9,0);
    for (int i=0;i<n;i++) 
    {
        cin>>a[i];
        cnt[a[i]-1]++;
    }

    int Mm=n/9,cnt_m=0;
    for (int c:cnt)
    {
        if (c>=Mm && c<=Mm+1)
        {
            if (c==Mm+1) cnt_m++;
        }
        else
        {
            cout<<"NO";
            return 0;
        }
    }
    if (cnt_m==n%9) cout<<"YES";
    else cout<<"NO";
    return 0;
}
// 64 位输出请用 printf("%lld")
发表于 2026-04-15 19:29:33 回复(0)
和我昨爱头像 和我昨爱 
0-9数字出现最多的次数必须比最少的次数相差1以内

#include <iostream>
#include <vector>
using namespace std;

int main(){

    int N;
    cin >> N;
    vector<int> nums={0,0,0,0,0,0,0,0,0};
    int max=0,min=N;
    int Q;
    while(N--){
        cin >> Q;
        nums[(int)(Q-1)]++;
    }
    for( int i=0;i<9;i++ ){
        max = max>nums[i]?max:nums[i];
        min = min<nums[i]?min:nums[i];
    }
    if(max-min<2){
        cout << "YES";
    }else{
        cout << "NO";
    }
    cout << endl;

    return 0;
}

发表于 2026-04-15 17:14:08 回复(0)
牛客542644049号头像 牛客542644049号 
n=int(input())
lst = list(map(int,input().split()))
result = "YES"
cnt_lst = []
for i in range(1,10):
    cnt_lst.append(lst.count(i))
     #简单理解为：重新排序后，去掉前面n//9个1~9的内容，还需要保证剩下部分不重复，但凡有一个重复就不满足条件
    if max(cnt_lst)-min(cnt_lst) >1:
        result = "NO"
print(result)


发表于 2026-04-15 17:05:03 回复(1)
G了的小龙虾很想拿头像 G了的小龙虾很想拿 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        //用于计数
        int[] count = new int[9];
        for(int i =0; i<n; i ++){
            int num =  in.nextInt();
            count[num-1]++;
        }
        int max = 0;
        int min = 1000000;
        //取计数最大最小值
        for(int c:count){
            max = Math.max(max,c);
            min = Math.min(min,c);
        }
        //差值0，1可行
        if(max - min == 1 || max - min == 0){
            System.out.print("YES");
        }else{
            System.out.print("NO");
        }
    }

发表于 2026-04-12 23:38:20 回复(0)
JavaScript Node
牛客453859736号头像 牛客453859736号
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    // Write your code here
    let lines = []
    while(line = await readline()){
        lines.push(line)
    }
    let total = lines[0]
    if(total < 9){
        console.log("NO")
        return
    }
    let arr = lines[1].split(" ")
    let count = parseInt(total/9)
    let count2 = total % 9
    function func(arr, i){
        return arr.filter(ele => ele == i).length
    }
    let numArr = []
    for(let i=1; i<=9; i++){
        numArr.push(
            func(arr,i)
        )
    }
    let flag1 = 0
    let flag2 = 0
    for(let i=0; i<numArr.length; i++){
        if(numArr[i] < count || numArr[i] > count+1){
            console.log("NO")
            return
        }else if(numArr[i] == count){
            flag1 += 1
        }else if(numArr[i] == count+1){
            flag2 += 1
        }
    }
    if(flag2 == count2){
        console.log("YES")
    }else{
        console.log("NO")
    }
}()

发表于 2026-03-29 15:17:53 回复(0)
reee11头像 reee11
这题好诡异，任取子串的话，得用滑动窗口吧，s[i]=s[i+9]才行吧，但是案例又不对
发表于 2026-02-19 15:47:18 回复(0)
juo1头像 juo1 
from collections import Counter 

n = int(input())
a = Counter(map(int, input().split()))

for i in range(1, 10):
    if i not in a:
        print('NO')
        exit(0)

most = a.most_common()
if most[0][1]-most[-1][1]>1:
    print('NO')
    exit(0)


print('YES')

发表于 2026-02-16 17:40:00 回复(0)
C++
爱看剧的花生米躺平又起来了头像 爱看剧的花生米躺平又起来了
#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    int n;
    cin>>n;
    int k=n/9;//完全包括1~9循环的个数
    int m=n%9;//完整循环之外多余的数
    int a;
    unordered_map<int,int>hash;
    for(int i=0;i<n;i++){
        cin>>a;
        hash[a]++;
    }
    //没有多余的数，1~9所有数出现次数都需要与循环个数相等
    if(m==0){
        for(const auto& it:hash){
            if(it.second!=k){
                cout<<"NO";
                return 0;
            }
        }
        cout<<"YES";
        return 0;
    }
    //存在多余的数，多余的数只能出现一次，即总出现次数为k+1;
    //多余的数在是否严格递进方面没有要求，比如多余2,4,9可以组成排列
    //2,4,9,1,3,5,6,7,8,2,4,9......2,4,9符合数独数组要求
    else {
        for(const auto& it:hash){
            if(it.second!=k+1&&it.second!=k){
                cout<<"NO";
                return 0;
            }
        }
        cout<<"YES";
        return 0;
    }
}
// 64 位输出请用 printf("%lld")
发表于 2026-02-13 22:04:39 回复(0)
赵金布头像 赵金布 
from collections import Counter
n=int(input())
list1=Counter(input().split())
if len(set(list1.values()))>2:
    print('NO')
else:
    print('YES')
Counter太好用了
发表于 2026-02-11 21:14:51 回复(0)
Python3
牛客559248288号头像 牛客559248288号
import sys

n = int(input())
a = list(map(int,input().split()))
b = sorted(set(a))
c = []
k = []
if len(b) != 9:
    print("NO")
else:
    flag = True
    for i in range(9):
        c.append(a.count(b[i]))
    for j in c:
        if j!=len(a)//9 and j!=len(a)//9+1:
            print('NO')
            flag = False
            break
    if flag:
        print("YES")
           
   
发表于 2025-12-26 02:22:11 回复(0)
C++
mulister张头像 mulister张 
#include <iostream>
#include <set>
#include <vector>
using namespace std;
bool find19(multiset<int> &s){
    for(int i=1;i<=9;i++){
        auto it=s.find(i);
        if(it==s.end()){return false;}
        else{s.erase(it);}
    }
    return true;
}
int main() {
    multiset<int> s;
    int n,m;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>m;
        s.insert(m);
    }
    while(s.size()>=9){
        if(!find19(s)){
            cout<<"NO";
            return 0;
        }
    }
    set<int> ss(s.begin(),s.end());
    if(ss.size()!=s.size()){
        cout<<"NO";
        return 0;
    }
    cout<<"YES";
    return 0;
}
// 64 位输出请用 printf("%lld")

发表于 2025-11-16 17:45:53 回复(0)
nothing5头像 nothing5
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int main() {

    int n;
    cin >> n;
    vector<int> vec;
    int temp;
    while (n--) {
        cin >> temp;
        vec.push_back( temp );
    }

    int num = 0;
    for (int i = 1; i <= 9; i++) {
        bool hasRequiredNum = false;
        for (int number : vec) {
            if ( i == number ) {
                hasRequiredNum = true;
                num++;
            }
        }
        if ( !hasRequiredNum ) {
            cout << "NO" << endl;   //1~9有数字不存在
            return 0;
        }
    }

    int group_num = vec.size() / 9;

    bool res = true;
    unordered_map<int, int> urd_map;
    for ( int i = 0; i < vec.size(); i++ ) {
        urd_map[ vec[i] ]++;
    }

    for ( auto map : urd_map ) {
        if ( ( map.second - group_num > 1 ) || ( map.second < group_num ) ) {
            res = false;
            break;
        }
    }

    if (res) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }

    return 0;
}
发表于 2025-10-21 22:10:37 回复(0)
Java
牛客916838684号头像 牛客916838684号
用总数除以9，保存余数yu和得数su。
需要有yu个数的出现次数为的su+1；
需要有9-yu个数的数的出现次数为su； 
import java.util.Scanner;
import java.util.TreeMap;
import java.util.TreeSet;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int nu = in.nextInt();

        char[] ch = new char[nu];

        TreeMap<Integer, Integer> tre = new TreeMap<>();

        int yu = nu%9;
        int su = nu/9;

        for(int i=0; i< nu;i++){
            int temp = in.nextInt();
            tre.put(temp, tre.getOrDefault(temp, 0)+1);
            // tre.add(in.nextInt());
        }

        int countA =0;
        int countB =0;

        for(Integer key : tre.keySet()){
            if(tre.get(key)>=su+1){
                countA++;
            }
            if(tre.get(key) == su){
                countB++;
            }
        }
        // System.out.println(countA);
        // System.out.println(countB);

        if(countA >= yu && countB ==9-yu){
            System.out.println("YES");
        }else{
            System.out.println("NO");

        }

    }
}


发表于 2025-10-07 17:29:48 回复(0)
Java
清浅QAQ头像 清浅QAQ
import java.util.*;
import java.io.*;
//其实就是最多最少个数差距不能超过1

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int[] arr = new int[10];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++){
            int temp = Integer.parseInt(st.nextToken());
            arr[temp]++;
        }
        int max = 0;
        int min = Integer.MAX_VALUE;
        for(int i = 1; i <= 9; i++){
            max = Math.max(arr[i], max);
            min = Math.min(arr[i], min);
        }
        System.out.println((max - min) > 1 ? "NO" : "YES");
        br.close();
    }
}
发表于 2025-09-17 17:00:19 回复(0)
提交观点

问题信息

模拟
难度：
31条回答 719浏览

热门推荐

相关试题

数独数组

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号