CCF202104 (第22次能力认证)java题解

题目一：灰度直方图

问题描述

一幅长宽分别为 n 个像素和 m 个像素的灰度图像可以表示为一个 n×m 大小的矩阵 A。
其中每个元素 Aij（0≤i<n、0≤j<m）是一个 [0,L) 范围内的整数，表示对应位置像素的灰度值。
具体来说，一个 8 比特的灰度图像中每个像素的灰度范围是 [0,128)。

一副灰度图像的灰度统计直方图（以下简称“直方图”）可以表示为一个长度为 L 的数组 h，其中 h[x]（0≤x<L）表示该图像中灰度值为 x 的像素个数。显然，h[0] 到 h[L−1] 的总和应等于图像中的像素总数 n⋅m。

已知一副图像的灰度矩阵 A，试计算其灰度直方图 h[0],h[1],⋯,h[L−1]。

输入格式

输入共 n+1 行。

输入的第一行包含三个用空格分隔的正整数 n、m 和 L，含义如前文所述。

第二到第 n+1 行输入矩阵 A。
第 i+2（0≤i<n）行包含用空格分隔的 m 个整数，依次为 Ai0,Ai1,⋯,Ai(m−1)。

输出格式

输出仅一行，包含用空格分隔的 L 个整数 h[0],h[1],⋯,h[L−1]，表示输入图像的灰度直方图。

样例输入

4 4 16
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15

Data

样例输出

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Data

样例输入

7 11 8
0 7 0 0 0 7 0 0 7 7 0
7 0 7 0 7 0 7 0 7 0 7
7 0 0 0 7 0 0 0 7 0 7
7 0 0 0 0 7 0 0 7 7 0
7 0 0 0 0 0 7 0 7 0 0
7 0 7 0 7 0 7 0 7 0 0
0 7 0 0 0 7 0 0 7 0 0

Data

样例输出

48 0 0 0 0 0 0 29

Data

评测用例规模与约定

全部的测试数据满足 0<n,m≤500 且 4≤L≤256。

思路

思路一：

题目的大意就是统计二维数组里的每个数的出现次数

这让我马上想到了HashMap

思路二：

将二维数组转化成一维数组，排序，然后用双指针法统计每个元素出现的个数

题解

这里只给出了思路一的写法，欢迎大家补充

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int L = sc.nextInt();
        HashMap<Integer, Integer> map = new HashMap<>();

        int[][] arr = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                arr[i][j] = sc.nextInt();
//---------------------用hashMap对二维数组的每个变量进行个数统计
                int count = 1;
                if (map.containsKey(arr[i][j])) {
                    count += map.get(arr[i][j]);
                    map.put(arr[i][j], count);
                } else {
                    map.put(arr[i][j], count);
                }
//-----------------------------------------------
            }
        }

        int []ans = new int[L];
        //将map里面的值拿出来，因为map里都是对象类型，所以要用相应的ArrayList存储
        ArrayList<Integer> keyArr = new ArrayList<Integer>(map.keySet());
        ArrayList<Integer> valueArr = new ArrayList<Integer>(map.values());
        //此处注意循环时i的取值范围，要和hash里面的数据范围对应
        for (int i = 0; i < keyArr.size(); i++) {
            ans[keyArr.get(i)] = valueArr.get(i);
        }
        for (int i = 0; i < L; i++) {
            System.out.print(ans[i]+" ");
        }


    }
}