home

หน้าแรก
 Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> Python

โปรแกรมหาพื้นที่ของเมทริกซ์ย่อยที่ใหญ่ที่สุดโดยการจัดเรียงคอลัมน์ใหม่ใน Python

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

ดังนั้นหากอินพุตเป็นแบบ

1 0 0
1 1 1
1 0 1

แล้วผลลัพธ์จะเป็น 4 เพราะเราสามารถจัดเรียงเป็น −

1 0 0
1 1 1
1 1 0

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

  • n :=จำนวนแถวของเมทริกซ์
  • m :=จำนวนคอลัมน์ของเมทริกซ์
  • ตอบ :=0
  • สำหรับฉันในช่วง 1 ถึง n - 1 ทำ
    • สำหรับ j ในช่วง 0 ถึง m - 1 ทำ
      • ถ้าเมทริกซ์[i, j] เป็น 1 แล้ว
        • เมทริกซ์[i, j] :=เมทริกซ์[i, j] + เมทริกซ์[i-1, j]
  • สำหรับแต่ละแถวในเมทริกซ์ ให้ทำ
    • เรียงแถว
    • สำหรับ j ในช่วง m-1 ถึง 0, ลดลง 1 ทำ
      • ans :=สูงสุดของ ans และ row[j] *(m - j)
  • คืนสินค้า

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

def solve(matrix):
   n, m = len(matrix), len(matrix[0])
   ans = 0
   for i in range(1, n) :
      for j in range(m) :
         if matrix[i][j] :
          matrix[i][j] += matrix[i-1][j]
   for row in matrix :
      row.sort()
      for j in range(m-1, -1, -1):
         ans = max(ans, row[j] *(m - j))
   return ans

matrix = [
[1, 0, 0],
[1, 1, 1],
[1, 0, 1]
]
print(solve(matrix))

อินพุต

[
[1, 0, 0],
[1, 1, 1],
[1, 0, 1]
]

ผลลัพธ์

4