0054. Spiral Matrix
- Nhãn: Mảng, Ma trận, Mô phỏng
- Độ khó: Trung bình
Tóm tắt đề bài
Mô tả: Cho một ma trận hai chiều kích thước .
Yêu cầu: Trả về tất cả các phần tử trong ma trận theo thứ tự xoắn ốc theo chiều kim đồng hồ.
Giải thích:
- .
- .
- .
- .
Ví dụ:
- Ví dụ 1:
- Ví dụ 2:
Ý tưởng giải quyết
Ý tưởng 1: Mô phỏng
- Sử dụng mảng để lưu trữ kết quả. Định nghĩa các biên trên, dưới, trái, phải.
- Tiếp theo, theo thứ tự ngược chiều kim đồng hồ, truy cập các phần tử từ biên.
- Khi hoàn thành việc truy cập biên hiện tại, cần cập nhật lại vị trí biên, thu hẹp phạm vi để tiện cho việc truy cập lần tiếp theo.
- Cuối cùng, trả về mảng kết quả .
Ý tưởng 1: Code
Ý tưởng 1: Độ phức tạp
- Độ phức tạp thời gian: . Trong đó và lần lượt là số hàng và số cột của ma trận hai chiều.
- Độ phức tạp không gian: . Nếu tính cả không gian sử dụng cho mảng kết quả, thì độ phức tạp không gian là . Nếu không tính, thì độ phức tạp không gian là .