华为OD机试 B卷 - 稀疏矩阵扫描 (C++ Python JAVA JS GO)

稀疏矩阵扫描

华为OD机试B卷 - 华为OD上机考试B卷 100分题型

华为OD机试真题目录点击查看: 华为OD机试真题题库目录｜机考题库 + 算法考点详解

题目描述

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

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

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

输入描述

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

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

输出描述

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

用例1

输入

3 3 1 0 0 0 1 0 0 0 1

输出

3 3

说明

给定的3*3矩阵里，每一行和每一列内都存在2个0，行宽3，列宽3，[3/2] = 1，因此稀疏行有3个，稀疏列有3个。

用例2

输入

5 3 -1 0 1 0 0 0 -1 0 0 0 -1 0 0 0 0

输出

5 3

说明

给定的5*3矩阵，每行里面0的个数大于等于1表示稀疏行，每列里面0的个数大于等于2表示稀疏行，所以有5个稀疏行,3个稀疏列。

题解

思路：模拟

1. 首先这个题目有点问题，结合题目和用例来看，判断稀疏的情况是行中0的个数大于等于行宽一半， 列中0的个数大于等于列宽一般就认为稀疏
2. 理明白1的规则之后，这道题就非常简单了，
3. 统计每行/列中0的次数，然后按照1的规则进行判断统计
4. 输出结果就行

c++

#include<iostream> #include<vector> #include<string> #include <utility> #include <sstream> #include<algorithm> #include<cmath> #include<map> using namespace std; int main() { int m , n; cin >> m >> n; vector<vector<int>> grid(m, vector<int>(n)); // 行0的个数 vector<int> zeroRowNum(m, 0); // 列0的个数 vector<int> zeroColNum(n, 0); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { cin >> grid[i][j]; if (grid[i][j] == 0) { zeroRowNum[i]++; zeroColNum[j]++; } } } // 计算满足条件的行和列 int rowResCount = 0, colResCount = 0; for (int i = 0; i < m; i++) { if (zeroRowNum[i] >= n / 2){ rowResCount++; } } for (int i = 0; i < n; i++) { if (zeroColNum[i] >= m / 2){ colResCount++; } } cout << rowResCount << endl; cout << colResCount << endl; }

JAVA

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[][] grid = new int[m][n]; // 行0的个数 int[] zeroRowNum = new int[m]; // 列0的个数 int[] zeroColNum = new int[n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { grid[i][j] = sc.nextInt(); if (grid[i][j] == 0) { zeroRowNum[i]++; zeroColNum[j]++; } } } // 计算满足条件的行和列 int rowResCount = 0, colResCount = 0; for (int i = 0; i < m; i++) { if (zeroRowNum[i] >= n / 2) { rowResCount++; } } for (int i = 0; i < n; i++) { if (zeroColNum[i] >= m / 2) { colResCount++; } } System.out.println(rowResCount); System.out.println(colResCount); } }

Python

m,n=map(int,input().split())grid=[]zeroRowNum=[0]*m# 行0的个数zeroColNum=[0]*n# 列0的个数foriinrange(m):row=list(map(int,input().split()))grid.append(row)forjinrange(n):ifrow[j]==0:zeroRowNum[i]+=1zeroColNum[j]+=1# 计算满足条件的行和列rowResCount=sum(1forxinzeroRowNumifx>=n//2)colResCount=sum(1forxinzeroColNumifx>=m//2)print(rowResCount)print(colResCount)

JavaScript

constreadline=require('readline');constrl=readline.createInterface({input:process.stdin,output:process.stdout,terminal:false});letlines=[];rl.on('line',(line)=>{lines.push(line.trim());});rl.on('close',()=>{let[m,n]=lines[0].split(' ').map(Number);letgrid=Array.from({length:m},()=>Array(n).fill(0));letzeroRowNum=Array(m).fill(0);// 行0的个数letzeroColNum=Array(n).fill(0);// 列0的个数for(leti=0;i<m;i++){letrow=lines[i+1].split(' ').map(Number);for(letj=0;j<n;j++){grid[i][j]=row[j];if(row[j]===0){zeroRowNum[i]++;zeroColNum[j]++;}}}// 计算满足条件的行和列letrowResCount=zeroRowNum.filter(x=>x>=Math.floor(n/2)).length;letcolResCount=zeroColNum.filter(x=>x>=Math.floor(m/2)).length;console.log(rowResCount);console.log(colResCount);});

Go

packagemainimport("fmt")funcmain(){varm,nintfmt.Scan(&m,&n)grid:=make([][]int,m)zeroRowNum:=make([]int,m)// 行0的个数zeroColNum:=make([]int,n)// 列0的个数fori:=0;i<m;i++{grid[i]=make([]int,n)forj:=0;j<n;j++{fmt.Scan(&grid[i][j])ifgrid[i][j]==0{zeroRowNum[i]++zeroColNum[j]++}}}// 计算满足条件的行和列rowResCount,colResCount:=0,0fori:=0;i<m;i++{ifzeroRowNum[i]>=n/2{rowResCount++}}fori:=0;i<n;i++{ifzeroColNum[i]>=m/2{colResCount++}}fmt.Println(rowResCount)fmt.Println(colResCount)}