【数据结构与算法】力扣刷题记之 稀疏数组

2024-02-09 19:12

本文主要是介绍【数据结构与算法】力扣刷题记之 稀疏数组,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 🎉🎉欢迎光临🎉🎉

🏅我是苏泽,一位对技术充满热情的探索者和分享者。🚀🚀

🌟特别推荐给大家我的最新专栏《数据结构与算法:初学者入门指南》📘📘

本专栏纯属为爱发电永久免费!!!

这是苏泽的个人主页可以看到我其他的内容哦👇👇

努力的苏泽icon-default.png?t=N7T8http://suzee.blog.csdn.net/

目录

深入理解稀疏数组

稀疏数组:概念与应用场景

第一节:稀疏数组的基础概念及应用场景

第二节:实现稀疏数组的转换与应用

实现稀疏数组的转换

通过稀疏数组恢复出原始的普通数组。具体恢复过程如下:

稀疏数组的恢复与应用

探讨稀疏数组在题目以及实际开发中的应用场景

题目描述

稀疏数组压缩与恢复算法

思路分析


深入理解稀疏数组

稀疏数组:概念与应用场景

第一节:稀疏数组的基础概念及应用场景

稀疏数组是一种特殊的数组数据结构,其特点是大部分元素为同一值或者为0。在实际应用中,稀疏数组常常被用来存储那些绝大多数元素为0的二维数据,如图像、矩阵等。一个典型的应用场景是图像处理中的位图压缩。

在不使用稀疏数组的情况下,如果直接用二维数组来表示稀疏性很高的数据结构,会导致大量的存储空间浪费和性能损耗。例如,对于一个大规模的稀疏矩阵,如果每个元素都占用存储空间,将会占用大量的存储空间。而且在处理这样的数据结构时,需要额外的时间复杂度来遍历和操作大量的0值元素。

引入稀疏数组可以有效解决上述问题。通过稀疏数组的存储方式,我们可以只存储非零元素及其位置信息,从而大大减少存储空间的占用。同时,在对稀疏数组进行操作时,可以极大地提高程序的运行效率。

第二节:实现稀疏数组的转换与应用

实现稀疏数组的转换

下面是一个简单的示例代码,用于将普通的二维数组转换为稀疏数组:

假设我们有一个普通的二维数组如下:

普通数组:

 [[0, 0, 0, 0, 0],
 [0, 5, 0, 0, 0],
 [0, 0, 8, 0, 0],
 [0, 0, 0, 0, 0]]

我们希望将这个普通数组转换为稀疏数组。转换过程中,我们需要记录非零元素的位置和数值,并在稀疏数组的第一行记录原始数组的行数、列数和非零元素个数。具体转换过程如下:

遍历原始数组,记录非零元素及其位置:

非零元素 (1, 1) 值为 5
非零元素 (2, 2) 值为 8
 

将记录的非零元素及其位置转换为稀疏数组:

稀疏数组:

[[4, 5, 2],  # 第一行记录原始数组的行数、列数和非零元素个数
 [1, 1, 5],  # 非零元素 (1, 1) 值为 5
 [2, 2, 8]]  # 非零元素 (2, 2) 值为 8

通过稀疏数组恢复出原始的普通数组。具体恢复过程如下:

  1. 根据稀疏数组的第一行信息创建一个全为0的普通数组。

  2. 遍历稀疏数组中的非零元素,根据其位置信息将对应的值填入新建的普通数组中。

def convert_to_sparse_array(arr):sparse_arr = []rows, cols = len(arr), len(arr[0])count = 0# 遍历原始数组,记录非零元素及其位置for i in range(rows):for j in range(cols):if arr[i][j] != 0:sparse_arr.append([i, j, arr[i][j]])count += 1# 在稀疏数组的第一行记录原始数组的行数、列数和非零元素个数sparse_arr.insert(0, [rows, cols, count])return sparse_arr

稀疏数组的恢复与应用

除了将普通数组转换为稀疏数组,我们还需要实现将稀疏数组恢复为普通数组的功能。下面是一个简单的示例代码:

def restore_from_sparse_array(sparse_arr):rows, cols, count = sparse_arr[0]restored_arr = [[0 for _ in range(cols)] for _ in range(rows)]for i in range(1, count+1):row, col, val = sparse_arr[i]restored_arr[row][col] = valreturn restored_arr

探讨稀疏数组在题目以及实际开发中的应用场景

稀疏数组在实际项目中有许多应用场景,如图像处理、文本搜索、语音识别等。其中,最常见的应用场景是图像处理中的位图压缩。

在算法题领域中,稀疏数组也有广泛的应用。例如力扣(LeetCode)中的73题矩阵置零,就可以使用稀疏数组来进行优化,减少存储空间的占用。

力扣(LeetCode)73题矩阵置零的原题如下:

题目描述

给定一个m x n的矩阵,如果一个元素为0,则将其所在行和列的所有元素都设为0。请使用原地算法。

示例 1:

输入:
[[1,1,1],[1,0,1],[1,1,1]
]
输出:
[[1,0,1],[0,0,0],[1,0,1]
]

示例 2:

输入:
[[0,1,2,0],[3,4,5,2],[1,3,1,5]
]
输出:
[[0,0,0,0],[0,4,5,0],[0,3,1,0]
]
// 稀疏数组压缩算法示例
void compress(int** ori_arr, int row, int col, int* arr_len, int*** com_arr) {int count = 0;for (int i = 0; i < row; ++i) {for (int j = 0; j < col; ++j) {if (ori_arr[i][j] != 0) {++count;}}}*com_arr = malloc((count + 1) * sizeof(int*));(*com_arr)[0] = malloc(3 * sizeof(int));(*com_arr)[0][0] = row;(*com_arr)[0][1] = col;(*com_arr)[0][2] = count;int index = 1;for (int i = 0; i < row; ++i) {for (int j = 0; j < col; ++j) {if (ori_arr[i][j] != 0) {(*com_arr)[index] = malloc(3 * sizeof(int));(*com_arr)[index][0] = i;(*com_arr)[index][1] = j;(*com_arr)[index][2] = ori_arr[i][j];++index;}}}*arr_len = count + 1;
}// 稀疏数组恢复算法示例
void restore(int** ori_arr, int* arr_len, int*** com_arr) {int row = (*com_arr)[0][0];int col = (*com_arr)[0][1];for (int i = 0; i < row; ++i) {for (int j = 0; j < col; ++j) {ori_arr[i][j] = 0;}}for (int i = 1; i < *arr_len; ++i) {int x = (*com_arr)[i][0];int y = (*com_arr)[i][1];int val = (*com_arr)[i][2];ori_arr[x][y] = val;}
}

稀疏数组压缩与恢复算法

思路分析

稀疏数组的压缩算法可以将数组进行压缩,从而减少存储空间的占用。具体来说,稀疏数组的压缩算法会按照一定的规则,将非零元素的值及其所在的位置信息记录下来,并将其存储为三元组的形式。

以下是稀疏数组的压缩算法思路:

  1. 遍历原始数组,统计非零元素的个数count。
  2. 创建一个新的二维数组com_arr,大小为(count + 1) * 3,其中count + 1表示非零元素的个数加上一行用于记录原始数组的行数、列数和非零元素的总个数。
  3. 将原始数组的行数、列数和非零元素的总个数分别存储在com_arr的第一行。
  4. 遍历原始数组,将非零元素的行、列和值存储在com_arr的后续行中。
  5. 返回压缩后的数组com_arr和非零元素的个数count + 1。

稀疏数组的恢复算法则是根据压缩时的规则将压缩后的数据恢复为原始的数组数据。

以下是稀疏数组的恢复算法思路:

  1. 根据压缩后的数组com_arr的第一行,获取原始数组的行数row、列数col。
  2. 创建一个新的二维数组ori_arr,大小为row * col,并将其所有元素初始化为0。
  3. 遍历com_arr的后续行,将非零元素的值和对应的位置信息恢复到ori_arr中。
  4. 返回恢复后的数组ori_arr。

 

这篇关于【数据结构与算法】力扣刷题记之 稀疏数组的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/695067

相关文章

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

C++一个数组赋值给另一个数组方式

《C++一个数组赋值给另一个数组方式》文章介绍了三种在C++中将一个数组赋值给另一个数组的方法:使用循环逐个元素赋值、使用标准库函数std::copy或std::memcpy以及使用标准库容器,每种方... 目录C++一个数组赋值给另一个数组循环遍历赋值使用标准库中的函数 std::copy 或 std::

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

C++初始化数组的几种常见方法(简单易懂)

《C++初始化数组的几种常见方法(简单易懂)》本文介绍了C++中数组的初始化方法,包括一维数组和二维数组的初始化,以及用new动态初始化数组,在C++11及以上版本中,还提供了使用std::array... 目录1、初始化一维数组1.1、使用列表初始化(推荐方式)1.2、初始化部分列表1.3、使用std::