Sắp xếp lại mảng 2 chiều để tăng trên hàng nhưng giảm dần trên cột (hoặc ngược lại)

[huytunguyen (nkishuu)]

Sắp xếp mảng 2 chiều tăng dần hoặc giảm dần thì em gán thành mảng 1 chiều rồi sắp xếp, nhưng vừa tăng vừa giảm thế này thì làm sao ạ

[SITUVN.gcd]

Vẫn đưa về 1 mảng và sắp xếp, sau đó “phân phối” cho từng ô cho hợp lý dựa vào “góc nhỏ/ lớn nhất”. . “Phân phối” theo đường chéo hướng vuông góc (chưa chắc là vuông).
VD:
Dòng tăng - Cột giảm
=>

• Góc nhỏ nhất: trái - dưới.
• Góc lớn nhất: phải - trên.
• Đường chéo là phải - dưới -> trái - trên (1) hoặc trái - trên -> phải - dưới (2).

Nhập:

13 68 11 45
72 25 52 35
10 52 91 46

Thành 1 mảng và sắp xếp:

10 11 13 25 35 45 46 52 52 68 72 91 

“Phân phối” từ “góc nhỏ nhất”: trái - dưới. Theo đường chéo (1).

Giá trị        Chỉ số
45 52 72 91    05 08 10 11
13 35 52 68    02 04 07 09
10 11 25 46    00 01 03 06

Hoặc hướng chéo ngược lại (2):

Giá trị        Chỉ số
25 46 68 91    03 06 09 11
11 35 52 72    01 04 07 10
10 13 45 52    00 02 05 08

---

Lý thuyết và kết quả là vậy, bạn tự “dịch” sang mã.

[rogp10]

Suy nghĩ thêm chút nữa thì mỗi hàng trong ma trận có thể chạy 1 for với O(mn) mem.

O(1) mem mới là chua