Java에서 원본 배열을 희소 배열로 변환하는 방법

1.이란?

예를 들어 11 * 11 주사위 놀이 보드가 있고 이를 시뮬레이션하기 위해 프로그램을 사용하려면 2차원 배열이어야 합니다. 그런 다음 1을 사용하여 검은 돌을 나타내고 2를 사용하여 흰 돌을 나타냅니다. 체스판에 검은 돌과 흰 돌이 하나만 있으면 이 2차원 배열에는 1과 2가 하나만 있고 나머지는 있습니다. 다음과 같이 체스 말을 나타내지 않는 의미 없는 0입니다.

0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 1 0 0 0 0 0 0
0 0 0 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
……

배열의 요소 대부분이 0이거나 동일한 값을 갖는 경우 희소 배열을 사용하여 배열을 저장할 수 있습니다. 왜 이런 일을 하는가? 공간을 절약할 수 있기 때문이죠.

2. 사용 방법은?

• 원래 배열에 몇 개의 행, 열 및 몇 개의 다른 값이 있는지 기록하세요.

• 소규모 배열에서 다른 값을 가진 요소의 행, 열 및 값을 기록하세요. .이 소규모 배열을 희소 배열이라고 합니다

3. 사례:

기존 6*7 원래 배열은 다음과 같습니다.

0   0   0   22   0   0   15
0   11  0   0    0   17   0
0   0   0  -6    0   0    0
0   0   0   0    0   39   0
91  0   0   0    0   0    0
0   0   28  0    0   0    0

먼저 희소 배열의 첫 번째 행과 열은 다음과 같습니다. 첫 번째 행과 두 번째 열에는 요소 배열의 행 수를 기록합니다. 원래 배열의 열 수를 기록합니다. 첫 번째 행과 세 번째 열은 원래 배열에 포함된 서로 다른 값의 수(0 제외)를 기록합니다. 따라서 희소 배열의 한 행은 다음과 같아야 합니다.

行    列    值
6     7     8

희소 배열의 두 번째 행부터 시작하여 각 행은 원래 배열에 있는 0이 아닌 값의 행, 열 및 값 크기를 기록합니다. 예를 들어 두 번째 줄이 원래 배열의 행, 열 및 값 22를 기록하는 것이라면 희소 배열의 두 번째 줄은 다음과 같습니다.

行    列    值
0     3     22

그런 다음 이 방법을 사용하여 15, 11, 17, -6, 39, 91, 28 정보이므로 원래 배열에서 최종적으로 변환된 희소 배열은 다음과 같습니다.

行    列    值
6     7     8
0     3     22
0     6     15
1     1     11
1     5     17
2     3     -6
3     5     39
4     0     91
5     2     28

이것은 6 * 7 배열을 9 * 3 배열로 변환하여 압축 효과를 얻습니다.

4. 원본 배열과 희소 배열 간의 변환 아이디어:

원래 배열을 희소 배열로 변환:

• 2차원 배열을 탐색하여 유효 배열 수를 구합니다. 개수를 기반으로 희소 배열 생성

  ;

• int[count + 1][3]유효한 배열을 희소 배열에 저장

• 희소 배열을 원래 배열로 저장:

희소 배열의 첫 번째 행을 읽으면 배열의 첫 번째 행을 기반으로 방법을 알 수 있습니다. 원본 배열에 있는 많은 행과 열. 그런 다음 원본 배열을 만듭니다.

• 희소 배열 뒤에 여러 행의 배열을 읽고 이를 원본 배열에 할당합니다.

public class SparseArray {
    public static void main(String[] args){
        // 创建一个 11 * 11的原始数组
        int[][] arr1 = new int[11][11];
        arr1[1][2] = 1;
        arr1[2][3] = 2;

        // 原始数组转稀疏数组
        // 1. 遍历，得到非0数据的个数以及所在的行列
        int count = 0;
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < arr1.length; i++) {
            for (int j = 0; j < arr1[i].length; j++) {
                if (arr1[i][j] != 0){
                    count ++;
                    map.put(i+ "," + j, arr1[i][j]);
                }
            }
        }
        // 2. 创建稀疏数组
        int[][] sparseArr = new int[count + 1][3];
        sparseArr[0][0] = arr1.length;
        sparseArr[0][1] = arr1[0].length;
        sparseArr[0][2] = count;
        // 3. 给稀疏数组赋值
        int row = 1;
        for (String key : map.keySet()){
            String[] ij = key.split(",");
            int i = Integer.parseInt(ij[0]);
            int j = Integer.parseInt(ij[1]);
            sparseArr[row][0] = i;
            sparseArr[row][1] = j;
            sparseArr[row][2] = map.get(key);
            row ++;
        }
        // 4. 遍历稀疏数组
        for (int i = 0; i < sparseArr.length; i++) {
            for (int j = 0; j < sparseArr[i].length; j++) {
                System.out.print(sparseArr[i][j] + "   ");
            }
            System.out.println("\r\n");
        }

        // 稀疏数组恢复原始数组
        // 1. 根据第一行第一列第二列创建出原始数组
        int i = sparseArr[0][0];
        int j = sparseArr[0][1];
        int[][] arr2 = new int[i][j];
        // 2. 给原始数组赋值
        for (int k = 1; k < sparseArr.length; k++) {
            int x = sparseArr[k][0];
            int y = sparseArr[k][1];
            int val = sparseArr[k][2];
            arr2[x][y] = val;
        }
        // 3. 遍历转换的数组
        for (int a = 0; a < arr2.length; a++) {
            for (int b = 0; b < arr2[a].length; b++) {
                System.out.print(arr2[a][b] + "   ");
            }
            System.out.println("\r\n");
        }
    }
}

위의 코드는 원래의 배열과 희소성을 구현합니다. 배열의 상호 변환과 희소 배열의 유연한 사용은 실행 메모리를 절약하고 프로그램 성능을 향상시킬 수 있습니다.

위 내용은 Java에서 원본 배열을 희소 배열로 변환하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!