หาสมาชิกที่แตกต่างกันซ้ำในทุกแถวของเมทริกซ์ใน C++

แนวคิด

ได้รับเมทริกซ์ m x m ให้หาสมาชิกที่แตกต่างกันซ้ำในทุกแถวของเมทริกซ์ สามารถแสดงสมาชิกในลำดับใดก็ได้

อินพุต

mat[][] = {{13, 2, 15, 4, 17}, {15, 3, 2, 4, 36}, {15, 2, 15, 4, 12}, {15, 26, 4, 3, 2}, {2, 19, 4, 22, 15}}

เอาต์พุต

2 4 15

วิธีการ

วิธีที่ 1: ใช้ 3 ลูปซ้อน ตรวจสอบว่าสมาชิกของแถวแรกมีในแถวถัดไปทุกแถวหรือไม่ Time Complexity O(m^3) อาจต้องการพื้นที่เพิ่มเพื่อควบคุมค่าซ้ำ

วิธีที่ 2: เรียงแถวทั้งหมดของเมทริกซ์แยกกันจากน้อยไปมาก จากนั้นใช้วิธีแก้ปัญหาหาสมาชิกร่วมใน 3 อาร์เรย์ที่เรียงแล้ว ตัวอย่างการนำไปใช้ด้านล่าง

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

// การนำไปใช้ C++ หาสมาชิกที่แตกต่างกันซ้ำในทุกแถวของเมทริกซ์
#include <bits/stdc++.h>
using namespace std;
const int MAX1 = 100;

// ฟังก์ชันเรียงแต่ละแถวแยกกันจากน้อยไปมาก
void sortRows1(int mat1[][MAX1], int m) {
    for (int i = 0; i < m; i++)
        sort(mat1[i], mat1[i] + m);
}

// ฟังก์ชันหาสมาชิกร่วมทั้งหมด
void findAndPrintCommonElements1(int mat1[][MAX1], int m) {
    // เรียงแถวแยกกัน
    sortRows1(mat1, m);
    // ดัชนีคอลัมน์ปัจจุบันของแต่ละแถวเก็บไว้
    // จากที่ค้นหาสมาชิกในแถวนั้น
    int curr_index1[m];
    memset(curr_index1, 0, sizeof(curr_index1));
    int f = 0;
    for (; curr_index1[0] < m; curr_index1[0]++) {
        // ค่าที่อยู่ที่ดัชนีคอลัมน์ปัจจุบันของแถวแรก
        int value1 = mat1[0][curr_index1[0]];
        bool present1 = true;
        // 'value' กำลังถูกค้นหาในแถวถัดไปทั้งหมด
        for (int i = 1; i < m; i++) {
            // วนลูปผ่านสมาชิกทั้งหมดของแถวจากดัชนีคอลัมน์ปัจจุบัน
            // จนกว่าจะพบสมาชิกมากกว่า 'value' หรือถึงท้ายแถว
            while (curr_index1[i] < m && mat1[i][curr_index1[i]] <= value1)
                curr_index1[i]++;
            // หากสมาชิกไม่ได้อยู่ที่คอลัมน์ก่อนหน้า 'curr_index' ของแถว
            if (mat1[i][curr_index1[i] - 1] != value1)
                present1 = false;
            // หากทุกสมาชิกของแถวถูกเดินทางหมดแล้ว
            if (curr_index1[i] == m) {
                f = 1;
                break;
            }
        }
        // หาก 'value' ร่วมในทุกแถว
        if (present1)
            cout << value1 << " ";
        // หากแถวไหนถูกเดินทางหมดแล้ว ไม่มีสมาชิกร่วมเพิ่มเติม
        if (f == 1)
            break;
    }
}

// โปรแกรมหลักทดสอบ
int main() {
    int mat1[][MAX1] = {{13, 2, 15, 4, 17}, {15, 3, 2, 4, 36}, {15, 2, 15, 4, 12}, {15, 26, 4, 3, 2}, {2, 19, 4, 22, 15}};
    int m = 5;
    findAndPrintCommonElements1(mat1, m);
    return 0;
}

เอาต์พุต

2 4 15