พลิกคอลัมน์เพื่อแถวเท่ากันสูงสุด (Flip Columns For Maximum Equal Rows) ใน Python

โจทย์: กำหนดเมทริกซ์ 0 และ 1 สามารถเลือกคอลัมน์ใดก็ได้และพลิกค่า (0↔1) ในคอลัมน์นั้นทั้งหมด หาจำนวนแถวสูงสุดที่มีค่าเท่ากันทุกคอลัมน์หลังจากพลิก

ตัวอย่าง

Matrix:

0 0 0
0 0 1
1 1 0

ข้อสังเกตสำคัญ

สองแถวจะกลายเป็นเหมือนกันหลังพลิกได้ ถ้าทั้งคู่:

• เหมือนกันเดิม, หรือ
• ตรงข้ามกันทุกคอลัมน์ (complement)

ดังนั้น ให้จับกลุ่มแถวที่ "เทียบเท่า" กัน (รวม complement) กลุ่มที่ใหญ่ที่สุด = คำตอบ

อัลกอริทึม

1. สำหรับแต่ละแถว สร้าง complement (XOR 1 ทุกคอลัมน์)
2. นับจำนวนแถวที่เท่ากับแถวปัจจุบันหรือ complement ของมัน
3. หาค่าสูงสุด

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

class Solution(object):
    def maxEqualRowsAfterFlips(self, matrix):
        max_rows = 0
        
        for row in matrix:
            # สร้าง complement ของแถวนี้
            complement = [1 - x for x in row]  # หรือ x ^ 1
            
            # นับแถวที่ตรงกับ row หรือ complement
            count = 0
            for other in matrix:
                if other == row or other == complement:
                    count += 1
            
            max_rows = max(max_rows, count)
        
        return max_rows

# ทดสอบ
ob = Solution()
print(ob.maxEqualRowsAfterFlips([[0,0,0],[0,0,1],[1,1,0]]))  # Output: 2

ตัวอย่าง Input/Output

Input: [[0,0,0],[0,0,1],[1,1,0]]
Output: 2

ความซับซ้อน: Time O(m²×n), Space O(n) - สามารถปรับปรุงเป็น O(m×n) ด้วย Hash Map ได้