稀疏数组的概念和使用
当在一个数组中同一元素的个数远远大于数组总个数的一半以上是,可以使用稀疏数组达到元素个数的缩减,表结构清晰易懂
稀疏数组结构
稀疏数组思路:
需要得出原数组的总的行数与列数,以及每个数的多少 及其行和列 将其整合在一起
import com.sun.javaws.IconUtil;
import java.util.Scanner;
/**
* @Description:稀疏数组的使用
* @Author:小黑洽
* @Date:2021/8/19
*/
public class Demo {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
/**
* 功能描述: <br>自定义数组
* @Param:
* @Return:
* @Author: 小黑洽
* @Date:
*/
int[][] array = new int[11][11];
array[2][4] = 7;
array[9][1] = 10;
array[5][6] = 33;
array[8][9] = 8;
int count = 0;
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[0].length; j++) {
//System.out.print(array[i][j]+" ");
if(array[i][j] != 0){
count++;
}
}
}
//将二维数组转化为稀疏数组
int[][] sparseArray = conversion(array,count);
for (int i = 0; i < sparseArray.length; i++) {
for (int j = 0; j < sparseArray[0].length; j++) {
System.out.print(sparseArray [i][j]+" ");
}
System.out.println();
}
//逆向稀疏数组
int[][] reverseArray= reverse(sparseArray);
for (int i = 0; i < reverseArray.length; i++) {
for (int j = 0; j < reverseArray[0].length; j++) {
System.out.print(reverseArray [i][j]+" ");
}
System.out.println();
}
}
/**
* 功能描述: <br>将二维数组转化为稀疏数组
* @Param:
* @Return:
* @Author: 小黑洽
* @Date:
*/
public static int[][] conversion(int[][] array,int count){
int[][] sparseArray = new int[count+1][3];
int t = 0;
sparseArray[0][0]=array.length;
sparseArray[0][1]=array[0].length;
sparseArray[0][2]=count;
t+=1;
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[0].length; j++) {
//System.out.print(array[i][j]+" ");
if(array[i][j] != 0){
sparseArray[t][0]=i;
sparseArray[t][1]=j;
sparseArray[t++][2]=array[i][j];
}
}
}
return sparseArray;
}
/**
* 功能描述: <br>稀疏数组解析
* @Param:
* @Return:
* @Author: 小黑洽
* @Date:
*/
public static int[][] reverse(int[][] sparseArray){
int row = sparseArray[0][0];
int col = sparseArray[0][1];
int count = sparseArray[0][2];
int[][] reverseArray = new int[row][col];
for (int i = 1; i < count+1 ; i++) {
reverseArray[sparseArray[i][0]][sparseArray[i][1]]=sparseArray[i][2];
}
return reverseArray;
}
}