หาหมายเลขแถวของเมทริกซ์ไบนารีที่มีจำนวน 1 มากที่สุดใน C++

ในปัญหานี้ เราได้รับเมทริกซ์ไบนารีที่แต่ละแถวถูกเรียงลำดับแล้ว งานของเราคือ หาหมายเลขแถวของเมทริกซ์ไบนารีที่มีจำนวน 1 มากที่สุด

มาดูตัวอย่างเพื่อเข้าใจปัญหา

Input

binMat[][] = { 
    1, 1, 1, 1 
    0, 0, 0, 0 
    0, 0, 0, 1 
    0, 0, 1, 1 
}

Output

1

วิธีแก้ปัญหา

วิธีแก้ที่ง่ายคือนับจำนวน 1 ทั้งหมดในแต่ละแถว และคืนค่าหมายเลขแถวที่มีจำนวน 1 มากที่สุด

โปรแกรมแสดงการทำงานของวิธีแก้

ตัวอย่าง (Naive)

#include <iostream> 
using namespace std; 
#define R 4 
#define C 4 

int findMax1Row(bool mat[R][C]) { 
    int max1Row = 0, max1Count = -1; 
    int i, index; 
    for (i = 0; i < R; i++) { 
        int oneCount = 0; 
        for(int j = 0; j < C; j++){ 
            if(mat[i][j]) 
                oneCount++; 
        } 
        if(oneCount > max1Count){ 
            max1Count = oneCount; 
            max1Row = i; 
        } 
    } 
    return (max1Row + 1); 
} 

int main() { 
    bool mat[R][C] = { 
        {0, 1, 1, 1}, 
        {0, 0, 1, 1}, 
        {0, 0, 0, 1}, 
        {0, 0, 0, 0} 
    }; 
    cout<<"The number of row with maximum number of 1's is "<<findMax1Row(mat); 
    return 0; 
}

ผลลัพธ์

The number of row with maximum number of 1's is 1

วิธีที่ดีกว่าคือใช้ binary search บนแต่ละแถวเพื่อหาการเกิดครั้งแรกของ 1 ในแถว จำนวน 1 ในแถวสามารถหาได้จากขนาดแถว - ดัชนีของ 1 ตัวแรก โดยใช้วิธีนี้ เราสามารถหาจำนวน 1 ในแต่ละแถวและคืนค่าแถวที่มีจำนวน 1 มากที่สุด

โปรแกรมแสดงการทำงานของวิธีแก้ (Binary Search)

ตัวอย่าง

#include <iostream> 
using namespace std; 
#define R 4 
#define C 4 

int binarySearch1Row(bool arr[], int start, int end) { 
    if(end >= start) { 
        int mid = start + (end - start)/2; 
        if ( ( mid == 0 || arr[mid-1] == 0) && arr[mid] == 1) 
            return mid; 
        else if (arr[mid] == 0) 
            return binarySearch1Row(arr, (mid + 1), end); 
        else 
            return binarySearch1Row(arr, start, (mid -1)); 
    } 
    return -1; 
} 

int findMax1Row(bool mat[R][C]) { 
    int max1Row = 0, max1Count = -1; 
    int i, index; 
    for (i = 0; i < R; i++) { 
        index = binarySearch1Row(mat[i], 0, C-1); 
        if (index != -1 && (C-index) > max1Count) { 
            max1Count = C - index; 
            max1Row = i; 
        } 
    } 
    return (max1Row + 1); 
} 

int main() { 
    bool mat[R][C] = { 
        {0, 1, 1, 1}, 
        {0, 0, 1, 1}, 
        {0, 0, 0, 1}, 
        {0, 0, 0, 0} 
    }; 
    cout<<"The number of row with maximum number of 1's is "<<findMax1Row(mat); 
    return 0; 
}

ผลลัพธ์

The number of row with maximum number of 1's is 1

การเพิ่มประสิทธิภาพในวิธีข้างต้นคือตรวจสอบว่าแถวปัจจุบันมี 1 มากกว่าแถวก่อนหน้าหรือไม่ โดยใช้ดัชนีของ 1 ตัวแรก ถ้ามีมากกว่า ให้ทำ binary search แต่จาก 0 ถึงดัชนีของ 1 ตัวแรกในแถวก่อนหน้า

นี่จะประหยัด overhead ในการคำนวณจำนวน 1 ในแถวที่มี 1 น้อยกว่าปัจจุบัน

โปรแกรมแสดงการทำงานของวิธีแก้ (Optimized)

ตัวอย่าง

#include <iostream> 
using namespace std; 
#define R 4 
#define C 4 

int binarySearch1Row(bool arr[], int start, int end) { 
    if(end >= start) { 
        int mid = start + (end - start)/2; 
        if ( ( mid == 0 || arr[mid-1] == 0) && arr[mid] == 1) 
            return mid; 
        else if (arr[mid] == 0) 
            return binarySearch1Row(arr, (mid + 1), end); 
        else 
            return binarySearch1Row(arr, start, (mid -1)); 
    } 
    return -1; 
} 

int findMax1Row(bool mat[R][C]) { 
    int i, index; 
    int max1Row = 0; 
    int max1Count = binarySearch1Row(mat[0], 0, C - 1); 
    for (i = 1; i < R; i++){ 
        if (max1Count != -1 && mat[i][C - max1Count - 1] == 1) { 
            index = binarySearch1Row (mat[i], 0, C - max1Count); 
            if (index != -1 && C - index > max1Count) { 
                max1Count = C - index; 
                max1Row = i; 
            } 
        } 
        else 
            max1Count = binarySearch1Row(mat[i], 0, C - 1); 
    } 
    return (max1Row + 1); 
} 

int main() { 
    bool mat[R][C] = { 
        {0, 1, 1, 1}, 
        {0, 0, 0, 1}, 
        {0, 0, 1, 1}, 
        {0, 0, 0, 0} 
    }; 
    cout<<"The number of row with maximum number of 1's is "<<findMax1Row(mat); 
    return 0; 
}

ผลลัพธ์

The number of row with maximum number of 1's is 1