潮州市网站建设_网站建设公司_网站建设_seo优化

(新卷,100分)- 矩阵稀疏扫描（Java & JS & Python & C）

题目描述

如果矩阵中的许多系数都为零，那么该矩阵就是稀疏的。对稀疏现象有兴趣是因为它的开发可以带来巨大的计算节省，并且在许多大的实践中都会出现矩阵稀疏的问题。

给定一个矩阵，现在需要逐行和逐列地扫描矩阵，如果某一行或者某一列内，存在连续出现的0的个数超过了行宽或者列宽的一半 [W /2] (整除) ，则认为该行或者该列是稀疏的。

扫描给定的矩阵，输出稀疏的行数和列数。

输入描述

第一行输入为M和N，表示矩阵的大小M*N，0 ＜ M ≤ 100，0 ＜ N ≤ 100

接下来M行输入为矩阵的成员，每行N个成员，矩阵成员都是有符号整数，范围-32,768到32,767

输出描述

输出两行，第一行表示稀疏行的个数，第二行表示稀疏列的个数

用例

题目解析

本题题目中说：

如果某一行或者某一列内，存在连续出现的0的个数超过了行宽或者列宽的一半 [W /2] (整除) ，则认为该行或者该列是稀疏的。

而用例里面对于稀疏行和稀疏列的确认，却不是根据连续0的个数，而是以0的个数（即不连续也可以）。

以用例说明为准（不以连续0为判断标准）（可得100%通过率）

我的解题思路是定义两个数组：

• rowZeroCount数组，长度为m，rowZeroCount[i] 代表第 i 行中含0个数
• colZeroCount数组，长度为n，colZeroCount[j] 代表第 j 列中含0个数

这样的话，只要遍历输入的矩阵matrix的每一个元素matrix[i][j]，

如果matrix[i][j]==0，那么说明在第 i 行找到一个0，此时rowZeroCount[i]++，以及在第 j 列找到一个0，此时colZeroCount[j]++。

最后，只要分别统计rowZeroCount中有多少个大于 n / 2，注意一行有n个元素，以及colZeroCount中有多个大于 m / 2，注意一列有m个元素。

Java算法源码

import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int m = sc.nextInt(); int n = sc.nextInt(); int[] rowZeroCount = new int[m]; int[] colZeroCount = new int[n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (sc.nextInt() == 0) { rowZeroCount[i]++; colZeroCount[j]++; } } } System.out.println(Arrays.stream(rowZeroCount).filter(val -> val >= n / 2).count()); System.out.println(Arrays.stream(colZeroCount).filter(val -> val >= m / 2).count()); } }

JS算法源码

/* JavaScript Node ACM模式 控制台输入获取 */ const readline = require("readline"); const rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); const lines = []; let m, n; rl.on("line", (line) => { lines.push(line); if (lines.length == 1) { [m, n] = lines[0].split(" ").map(Number); } if (m && lines.length == m + 1) { lines.shift(); const matrix = lines.map((s) => s.split(" ").map(Number)); getResult(m, n, matrix); lines.length = 0; } }); function getResult(m, n, matrix) { const rowZeroCount = new Array(m).fill(0); const colZeroCount = new Array(n).fill(0); for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { if (matrix[i][j] == 0) { rowZeroCount[i]++; colZeroCount[j]++; } } } console.log(rowZeroCount.filter((val) => val >= Math.floor(n / 2)).length); console.log(colZeroCount.filter((val) => val >= Math.floor(m / 2)).length); }

Python算法源码

# 输入获取 m, n = map(int, input().split()) matrix = [list(map(int, input().split())) for _ in range(m)] # 算法入口 def getResult(): rowZeroCount = [0] * m colZeroCount = [0] * n for i in range(m): for j in range(n): if matrix[i][j] == 0: rowZeroCount[i] += 1 colZeroCount[j] += 1 print(len(list(filter(lambda val: val >= n // 2, rowZeroCount)))) print(len(list(filter(lambda val: val >= m // 2, colZeroCount)))) # 算法调用 getResult()

C算法源码

#include <stdio.h> #define MAX_ROWS 100 #define MAX_COLS 100 int filter(int* arr, int arr_length, int threhold); int main() { // 输入获取 int m, n; scanf("%d %d", &m, &n); // 记录对应行中值为0的元素的个数 int rowZeroCount[MAX_ROWS] = {0}; // 记录对应列中值为0的元素的个数 int colZeroCount[MAX_COLS] = {0}; for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { // 矩阵元素获取 int num; scanf("%d", &num); // 如果矩阵元素值为0，则对应行（第 i 行）含0个数++，对应列（第 j 列）含0个数++ if(num == 0) { rowZeroCount[i]++; colZeroCount[j]++; } } } // 一行共有n个元素，如果对应行值为0的元素超过n/2个，即为稀疏行 printf("%d\n", filter(rowZeroCount, m, n / 2)); // 一列共有m个元素，只要对应列值为0的元素超过m/2个，即为稀疏列 printf("%d\n", filter(colZeroCount, n, m / 2)); return 0; } // 统计数组arr中大于等于threhold的元素的个数 int filter(int* arr, int arr_length, int threhold) { int count = 0; for(int i=0; i<arr_length; i++) { if(arr[i] >= threhold) { count++; } } return count; }

以题目描述为准（以连续0为判断标准）

我的解题思路是定义两个数组：

• rowZeroConstantMaxCount数组，长度为m，rowZeroConstantMaxCount[i] 代表第 i 行中连续0的最大个数
• colZeroConstantMaxCount数组，长度为n，colZeroConstantMaxCount[j] 代表第 j 列中连续0的最大个数

同时定义两个中间数组：

• rowZeroConstantCount数组，长度为m，rowZeroConstantCount[i] 代表第 i 行中各段连续0的个数
• colZeroConstantCount数组，长度为n，colZeroConstantCount[j] 代表第 j 列中各段连续0的个数

这样的话，只要遍历输入的矩阵matrix的每一个元素matrix[i][j]，

如果matrix[i][j]==0，那么说明：

• 在第 i 行找到一个0，此时rowZeroConstantCount[i]++，即第i行的连续0个数+1，另外还要比较记录最大连续0个数，更新rowZeroConstantMaxCount[i]中
• 在第 j 列找到一个0，此时colZeroConstantCount[j]++，即第i列的连续0个数+1，另外还要比较记录最大连续0个数，更新colZeroConstantMaxCount[i]中

如果matrix[i][j] != 0，那么说明：

• 在第 i 行连续0中断，此时rowZeroConstantCount[i]=0
• 在第 j 列连续0中断，此时colZeroConstantCount[j]=0

最后，只要分别统计rowZeroConstantMaxCount中有多少个大于 n / 2，注意一行有n个元素，以及olZeroConstantMaxCount中有多个大于 m / 2，注意一列有m个元素。

Java算法源码

import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int m = sc.nextInt(); int n = sc.nextInt(); // 临时记录每行的连续0个数 int[] rowConstantZeroCount = new int[m]; // 临时记录每列的连续0个数 int[] colConstantZeroCount = new int[n]; // 记录每行的最大连续0个数 int[] rowConstantZeroMaxCount = new int[m]; // 记录每列的最大连续0个数 int[] colConstantZeroMaxCount = new int[n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (sc.nextInt() == 0) { // 如果第i行，第j列为0, 则第i行连续0个数+1，第j列连续0个数+1 rowConstantZeroCount[i] += 1; rowConstantZeroMaxCount[i] = Math.max(rowConstantZeroMaxCount[i], rowConstantZeroCount[i]); colConstantZeroCount[j] += 1; colConstantZeroMaxCount[j] = Math.max(colConstantZeroMaxCount[j], colConstantZeroCount[j]); } else { // 如果如果第i行，第j列不为0,则第i行连续0中断，第j列连续0中断 rowConstantZeroCount[i] = 0; colConstantZeroCount[j] = 0; } } } System.out.println(Arrays.stream(rowConstantZeroMaxCount).filter(val -> val >= n / 2).count()); System.out.println(Arrays.stream(colConstantZeroMaxCount).filter(val -> val >= m / 2).count()); } }

JS算法源码

/* JavaScript Node ACM模式 控制台输入获取 */ const readline = require("readline"); const rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); const lines = []; let m, n; rl.on("line", (line) => { lines.push(line); if (lines.length == 1) { [m, n] = lines[0].split(" ").map(Number); } if (m && lines.length == m + 1) { lines.shift(); const matrix = lines.map((s) => s.split(" ").map(Number)); getResult(m, n, matrix); lines.length = 0; } }); function getResult(m, n, matrix) { // 临时记录每行的连续0个数 const rowConstantZeroCount = new Array(m).fill(0); // 临时记录每列的连续0个数 const colConstantZeroCount = new Array(n).fill(0); // 记录每行的最大连续0个数 const rowConstantZeroMaxCount = new Array(m).fill(0); // 记录每列的最大连续0个数 const colConstantZeroMaxCount = new Array(n).fill(0); for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { if (matrix[i][j] == 0) { // 如果第i行，第j列为0, 则第i行连续0个数+1，第j列连续0个数+1 rowConstantZeroCount[i]++; rowConstantZeroMaxCount[i] = Math.max( rowConstantZeroMaxCount[i], rowConstantZeroCount[i] ); colConstantZeroCount[j]++; colConstantZeroMaxCount[j] = Math.max( colConstantZeroMaxCount[j], colConstantZeroCount[j] ); } else { // 如果如果第i行，第j列不为0,则第i行连续0中断，第j列连续0中断 rowConstantZeroCount[i] = 0; colConstantZeroCount[j] = 0; } } } console.log( rowConstantZeroMaxCount.filter((val) => val >= Math.floor(n / 2)).length ); console.log( colConstantZeroMaxCount.filter((val) => val >= Math.floor(m / 2)).length ); }

Python算法源码

# 输入获取 m, n = map(int, input().split()) matrix = [list(map(int, input().split())) for _ in range(m)] # 算法入口 def getResult(): # 临时记录每行的连续0个数 rowConstantZeroCount = [0] * m # 临时记录每列的连续0个数 colConstantZeroCount = [0] * n # 记录每行的最大连续0个数 rowConstantZeroMaxCount = [0] * m # 记录每列的最大连续0个数 colConstantZeroMaxCount = [0] * n for i in range(m): for j in range(n): if matrix[i][j] == 0: # 如果第i行，第j列为0, 则第i行连续0个数+1，第j列连续0个数+1 rowConstantZeroCount[i] += 1 rowConstantZeroMaxCount[i] = max(rowConstantZeroMaxCount[i], rowConstantZeroCount[i]) colConstantZeroCount[j] += 1 colConstantZeroMaxCount[j] = max(colConstantZeroMaxCount[j], colConstantZeroCount[j]) else: # 如果如果第i行，第j列不为0,则第i行连续0中断，第j列连续0中断 rowConstantZeroCount[i] = 0 colConstantZeroCount[j] = 0 print(len(list(filter(lambda val: val >= n // 2, rowConstantZeroMaxCount)))) print(len(list(filter(lambda val: val >= m // 2, colConstantZeroMaxCount)))) # 算法调用 getResult()

C算法源码

#include <stdio.h> #define MAX_ROWS 100 #define MAX_COLS 100 #define MAX(a,b) a > b ? a : b int filter(int* arr, int arr_length, int threhold); int main() { // 输入获取 int m, n; scanf("%d %d", &m, &n); // 临时记录每行的连续0个数 int rowConstantZeroCount[MAX_ROWS] = {0}; // 临时记录每列的连续0个数 int colConstantZeroCount[MAX_COLS] = {0}; // 记录每行的最大连续0个数 int rowConstantZeroMaxCount[MAX_ROWS] = {0}; // 记录每列的最大连续0个数 int colConstantZeroMaxCount[MAX_COLS] = {0}; for(int i=0; i<m; i++) { for(int j=0; j<n; j++) { int num; scanf("%d", &num); if(num == 0) { // 如果第i行，第j列为0, 则第i行连续0个数+1，第j列连续0个数+1 rowConstantZeroCount[i] += 1; rowConstantZeroMaxCount[i] = MAX(rowConstantZeroMaxCount[i], rowConstantZeroCount[i]); colConstantZeroCount[j] += 1; colConstantZeroMaxCount[j] = MAX(colConstantZeroMaxCount[j], colConstantZeroCount[j]); } else { // 如果如果第i行，第j列不为0,则第i行连续0中断，第j列连续0中断 rowConstantZeroCount[i] = 0; colConstantZeroCount[j] = 0; } } } // 一行共有n个元素，如果对应行最大连续0的元素超过n/2个，即为稀疏行 printf("%d\n", filter(rowConstantZeroMaxCount, m, n / 2)); // 一列共有m个元素，只要对应列最大连续0的元素超过m/2个，即为稀疏列 printf("%d\n", filter(colConstantZeroMaxCount, n, m / 2)); return 0; } // 统计数组arr中大于等于threhold的元素的个数 int filter(int* arr, int arr_length, int threhold) { int count = 0; for(int i=0; i<arr_length; i++) { if(arr[i] >= threhold) { count++; } } return count; }