当前位置： 2024华为OD机试题库 (B卷,100分)- 矩阵稀疏扫描（Java & JS & Python & C）

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

2024-05-07 10

题目描述

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

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

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

输入描述

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

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

输出描述

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

用例

输入 3 3
1 0 0
0 1 0
0 0 1
输出

3
3
说明 给定的3*3矩阵里，每一行和每一列内都存在2个0，行宽3，列宽3，[3/2] = 1，因此稀疏行有3个，稀疏列有3个。
输入 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个稀疏列。

题目解析

本题题目中说：

如果某一行或者某一列内，存在连续出现的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("%dn", filter(rowZeroCount, m, n / 2));
// 一列共有m个元素，只要对应列值为0的元素超过m/2个，即为稀疏列
printf("%dn", 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("%dn", filter(rowConstantZeroMaxCount, m, n / 2));
// 一列共有m个元素，只要对应列最大连续0的元素超过m/2个，即为稀疏列
printf("%dn", 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;
}

 

免责声明：

1、IT资源小站为非营利性网站，全站所有资料仅供网友个人学习使用，禁止商用
2、本站所有文档、视频、书籍等资料均由网友分享，本站只负责收集不承担任何技术及版权问题
3、如本帖侵犯到任何版权问题，请立即告知本站，本站将及时予与删除下载链接并致以最深的歉意
4、本帖部分内容转载自其它媒体，但并不代表本站赞同其观点和对其真实性负责
5、一经注册为本站会员，一律视为同意网站规定，本站管理员及版主有权禁止违规用户
6、其他单位或个人使用、转载或引用本文时必须同时征得该帖子作者和IT资源小站的同意
7、IT资源小站管理员和版主有权不事先通知发贴者而删除本文

0

评论0

取消

首页 发现 VIP 我的

站点公告

没有账号？注册  忘记密码？