Array -- fancy traversal technique of two-dimensional array

along / Rotate the matrix counterclockwise

Rotating a two-dimensional array is a common written test question , Force to buckle 48 topic 「 Rotated image 」 It's a classic one ：

The subject is well understood , Is to let you rotate a two-dimensional matrix clockwise 90 degree , The difficulty is to 「 In situ 」 modify

Before talking about clever solutions , Let's first look at another algorithm problem that Google has tested to warm up ：

Give you a string containing several words and spaces s, Please write an algorithm , In situ Reverse the order of all words .

for instance , Enter such a string for you ：

s = "hello world labuladong"

Your algorithm needs to reverse the word order in the string in place ：

s = "labuladong world hello"

The usual way is to put s By space split Into several words , then reverse The order of these words , Finally, put these words join Form a sentence . But this method uses extra space , Not at all 「 Reverse in place 」 word .

The right thing to do is , First, the whole string s reverse ：

s = "gnodalubal dlrow olleh"

Then invert each word separately ：

s = "labuladong world hello"

The reason for the above question is to explain , Sometimes our conventional thinking of patting our heads , In the eyes of computers, it may not be the most elegant ; But computers think the most elegant thinking , It's not so intuitive for us

Back to the problem of clockwise rotation of two-dimensional matrix , The conventional idea is to find the mapping law between the original coordinates and the rotated coordinates , But can we make our minds jump , Try to invert the matrix 、 Mirror symmetry and other operations , There may be new breakthroughs .

We can first n x n matrix matrix Mirror symmetry according to the diagonal line from top left to bottom right ：

**
Then invert each row of the matrix ：**

The result is matrix Clockwise rotation 90 The result of degree ：

Translate the above ideas into code , Can solve the problem ：

//  Rotate the two-dimensional matrix clockwise in place  90  degree 
public void rotate(int[][] matrix) {
    
    int n = matrix.length;
    //  First mirror the symmetrical two-dimensional matrix along the diagonal 
    for (int i = 0; i < n; i++) {
    
        for (int j = i; j < n; j++) {
    
            // swap(matrix[i][j], matrix[j][i]);
            int temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }
    //  Then invert each row of the two-dimensional matrix 
    for (int[] row : matrix) {
    
        reverse(row);
    }
}

//  Invert a one-dimensional array 
void reverse(int[] arr) {
    
    int i = 0, j = arr.length - 1;
    while (j > i) {
    
        // swap(arr[i], arr[j]);
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        i++;
        j--;
    }
}

There must be readers who will ask , If you haven't done this problem , How can you think of this idea ？

Think carefully , The difficulty of rotating a two-dimensional matrix is to 「 That's ok 」 become 「 Column 」, take 「 Column 」 become 「 That's ok 」, This can be easily done only by following the diagonal symmetry operation , After symmetrical operation, it is easy to find the law .

Spiral traversal of matrix

My official account dynamic planning series often need to traverse two dimensions dp Array , But the difficulty lies in the state transition equation rather than the traversal of the array , At most, it is traversal in reverse order .

But next, let's talk about Li Kedi 54 topic 「 Spiral matrix 」, Take a look at how a two-dimensional matrix can be traversed in a fancy way ：

The core idea of problem solving is to follow the right 、 Next 、 Left 、 Traverse the array in the order of , And use four variables to delineate the boundary of non traversed elements ：

With spiral traversal , The corresponding boundary will shrink , Until the spiral traverses the entire array ：

List<Integer> spiralOrder(int[][] matrix) {
    
    int m = matrix.length, n = matrix[0].length;
    int upper_bound = 0, lower_bound = m - 1;
    int left_bound = 0, right_bound = n - 1;
    List<Integer> res = new LinkedList<>();
    // res.size() == m * n  Then traverse the entire array 
    while (res.size() < m * n) {
    
        if (upper_bound <= lower_bound) {
    
            //  Traverse from left to right at the top 
            for (int j = left_bound; j <= right_bound; j++) {
    
                res.add(matrix[upper_bound][j]);
            }
            //  Move the upper boundary down 
            upper_bound++;
        }
        
        if (left_bound <= right_bound) {
    
            //  Traverse from top to bottom on the right 
            for (int i = upper_bound; i <= lower_bound; i++) {
    
                res.add(matrix[i][right_bound]);
            }
            //  Move the right border to the left 
            right_bound--;
        }
        
        if (upper_bound <= lower_bound) {
    
            //  Traverse from right to left at the bottom 
            for (int j = right_bound; j >= left_bound; j--) {
    
                res.add(matrix[lower_bound][j]);
            }
            //  Move lower boundary up 
            lower_bound--;
        }
        
        if (left_bound <= right_bound) {
    
            //  Traverse from bottom to top on the left 
            for (int i = lower_bound; i >= upper_bound; i--) {
    
                res.add(matrix[i][left_bound]);
            }
            //  Move left border right 
            left_bound++;
        }
    }
    return res;
}

Force to buckle 59 topic 「 Spiral matrix II」 Is a similar topic , It's just the opposite , Let you generate the matrix in spiral order ：

Just change the above code a little ：

int[][] generateMatrix(int n) {
    
    int[][] matrix = new int[n][n];
    int upper_bound = 0, lower_bound = n - 1;
    int left_bound = 0, right_bound = n - 1;
    //  You need to fill in the numbers of the matrix 
    int num = 1;
    
    while (num <= n * n) {
    
        if (upper_bound <= lower_bound) {
    
            //  Traverse from left to right at the top 
            for (int j = left_bound; j <= right_bound; j++) {
    
                matrix[upper_bound][j] = num++;
            }
            //  Move the upper boundary down 
            upper_bound++;
        }
        
        if (left_bound <= right_bound) {
    
            //  Traverse from top to bottom on the right 
            for (int i = upper_bound; i <= lower_bound; i++) {
    
                matrix[i][right_bound] = num++;
            }
            //  Move the right border to the left 
            right_bound--;
        }
        
        if (upper_bound <= lower_bound) {
    
            //  Traverse from right to left at the bottom 
            for (int j = right_bound; j >= left_bound; j--) {
    
                matrix[lower_bound][j] = num++;
            }
            //  Move lower boundary up 
            lower_bound--;
        }
        
        if (left_bound <= right_bound) {
    
            //  Traverse from bottom to top on the left 
            for (int i = lower_bound; i >= upper_bound; i--) {
    
                matrix[i][left_bound] = num++;
            }
            //  Move left border right 
            left_bound++;
        }
    }
    return matrix;
}