home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

หมุนเมทริกซ์ 90 องศาโดยไม่ใช้พื้นที่เพิ่มเติมใน C++

เราได้รับอาร์เรย์ 2 มิติที่จะนำมาใช้สร้างรูปแบบเมทริกซ์ งานคือการหมุนเมทริกซ์ 90 องศาในทิศทางตรงข้ามเข็มนาฬิกา (Anti-clockwise) โดยที่แถวแรกจะกลายเป็นคอลัมน์แรก แถวที่สองกลายเป็นคอลัมน์ที่สอง และแถวที่สามกลายเป็นคอลัมน์ที่สาม และความท้าทายคือเราไม่ได้ใช้พื้นที่เพิ่มเติม (Extra Space)

ดูสถานการณ์ Input-Output ต่างๆ

Input -

int arr[row_col_size][row_col_size] = { { 5, 1, 4}, { 9, 16, 12 }, { 2, 8, 9}}

Output** -

Rotation of a matrix by 90 degree without using any extra space is: 4 12 9 1 16 8 5 9 2

คำอธิบาย - เราได้รับอาร์เรย์ 2 มิติแบบจำนวนเต็ม ตอนนี้เราจะหมุนเมทริกซ์ 90 องศาในทิศทางตามเข็มนาฬิกา (Clockwise)

Before rotation-: { { 5, 1, 4}, { 9, 16, 12 }, { 2, 8, 9}} After rotation-: 2 12 9 1 16 8 5 9 2

Input -

int arr[row_col_size][row_col_size] = { { 2, 1, 9}, { 11, 6, 32 }, { 3, 7, 5}}

Output** -

Rotation of a matrix by 90 degree in clockwise direction without using any extra space is: 9 32 5 1 6 7 2 7 3

คำอธิบาย - เราได้รับอาร์เรย์ 2 มิติแบบจำนวนเต็ม ตอนนี้เราจะหมุนเมทริกซ์ 90 องศาในทิศทางตามเข็มนาฬิกา

Before rotation-: { { 2, 1, 9}, { 11, 6, 32 }, { 3, 7, 5}} After rotation-: 9 32 5 1 6 7 2 7 3

วิธีการที่ใช้ในโปรแกรมด้านล่าง

1. วิธี Naive (Naive Approach)

  • รับอาร์เรย์จำนวนเต็ม 2 มิติที่จะถือเป็นเมทริกซ์ด้วย row_col_size

  • ส่งข้อมูลไปยังฟังก์ชัน Rotate_ClockWise(arr)

  • ภายในฟังก์ชัน Rotate_ClockWise(arr)

    • เริ่มลูป FOR จาก i=0 ถึง i น้อยกว่า row_col_size/2

    • ภายในลูป เริ่มลูป FOR อีกอันจาก j=i ถึง j น้อยกว่า row_col_size-i-1

    • ภายในลูป ตั้งค่า ptr = arr[i][j], arr[i][j] = arr[row_col_size-1-j][i], arr[row_col_size-1-j][i] = arr[row_col_size-1-i][row_col_size-1-j], arr[row_col_size-1-i][row_col_size-1-j] = arr[j][row_col_size-1-i] และ arr[j][row_col_size-1-i] = ptr

  • เริ่มลูป FOR จาก i=0 ถึง i น้อยกว่า row_col_size ภายในลูป เริ่มลูป FOR อีกอันจาก j=0 ถึง j น้อยกว่า row_col_size; j++ และพิมพ์ arr[i][j]

2. วิธีที่มีประสิทธิภาพ (Efficient Approach)

  • รับอาร์เรย์จำนวนเต็ม 2 มิติที่จะถือเป็นเมทริกซ์ด้วย row_col_size

  • ส่งข้อมูลไปยังฟังก์ชัน Rotate_ClockWise(arr)

  • ภายในฟังก์ชัน Rotate_ClockWise(arr)

    • เริ่มลูป FOR จาก i=0 ถึง i น้อยกว่า row_col_size

    • ภายในลูป เริ่มลูป FOR อีกอันจาก j=0 ถึง j น้อยกว่า row_col_size-i

    • ภายในลูป ตั้งค่า ptr = arr[i][j], arr[i][j] = arr[row_col_size-1-j][row_col_size-1-i] และ [row_col_size-1-j] ต่อ arr[j][row_col_size-1-i] ถึง ptr

    • เริ่มลูป FOR จาก i=0 ถึง i น้อยกว่า row_col_size/2 ภายในลูป เริ่มลูป FOR อีกอันจาก j=0 ถึง j น้อยกว่า row_col_size ภายในลูป ตั้งค่า ptr = arr[i][j], arr[i][j] = arr[row_col_size-1-i][j] และ arr[row_col_size-1-i][j] = ptr

  • เริ่มลูป FOR จาก i=0 ถึง i น้อยกว่า row_col_size ภายในลูป เริ่มลูป FOR อีกอันจาก j=0 ถึง j น้อยกว่า row_col_size; j++ และพิมพ์ arr[i][j]

Naive Approach

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;
#define row_col_size 3

void Rotate_ClockWise(int arr[row_col_size][row_col_size]) {
    for(int i = 0; i < row_col_size / 2; i++) {
        for(int j = i; j < row_col_size - i - 1; j++) {
            int ptr = arr[i][j];
            arr[i][j] = arr[row_col_size - 1 - j][i];
            arr[row_col_size - 1 - j][i] = arr[row_col_size - 1 - i][row_col_size - 1 - j];
            arr[row_col_size - 1 - i][row_col_size - 1 - j] = arr[j][row_col_size - 1 - i];
            arr[j][row_col_size - 1 - i] = ptr;
        }
    }
}

int main() {
    int arr[row_col_size][row_col_size] = { { 5, 1, 4}, { 9, 16, 12 }, { 2, 8, 9} };
    Rotate_ClockWise(arr);
    cout<<"Rotation of a matrix by 90 degree in clockwise direction without using any extra space is: \n";
    for(int i = 0; i < row_col_size; i++) {
        for(int j = 0; j < row_col_size; j++) {
            cout << arr[i][j] << " ";
        }
        cout << '\n';
    }
    return 0;
}

ผลลัพธ์

หากเรารันโค้ดข้างต้น จะได้ผลลัพธ์ดังนี้:

Rotation of a matrix by 90 degree in clockwise direction without using any extra space is: 2 9 5 8 16 1 9 12 4

Efficient Approach

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;
#define row_col_size 3

void Rotate_ClockWise(int arr[row_col_size][row_col_size]) {
    for(int i = 0; i < row_col_size; i++) {
        for(int j = 0; j < row_col_size - i; j++) {
            int ptr = arr[i][j];
            arr[i][j] = arr[row_col_size - 1 - j][row_col_size - 1 - i];
            arr[row_col_size - 1 - j][row_col_size - 1 - i] = ptr;
        }
    }
    for(int i = 0; i < row_col_size / 2; i++) {
        for(int j = 0; j < row_col_size; j++) {
            int ptr = arr[i][j];
            arr[i][j] = arr[row_col_size - 1 - i][j];
            arr[row_col_size - 1 - i][j] = ptr;
        }
    }
}

int main() {
    int arr[row_col_size][row_col_size] = { { 5, 1, 4}, { 9, 16, 12 }, { 2, 8, 9} };
    Rotate_ClockWise(arr);
    cout<<"Rotation of a matrix by 90 degree in clockwise direction without using any extra space is: \n";
    for(int i = 0; i < row_col_size; i++) {
        for(int j = 0; j < row_col_size; j++) {
            cout << arr[i][j] << " ";
        }
        cout << '\n';
    }
    return 0;
}

ผลลัพธ์

หากเรารันโค้ดข้างต้น จะได้ผลลัพธ์ดังนี้:

Rotation of a matrix by 90 degree in clockwise direction without using any extra space is: 2 9 5 8 16 1 9 12 4