238. Product of Array Except Self
- Tags: Mảng, Tổng tiền tố
- Độ khó: Trung bình
Tóm tắt đề bài
Mô tả: Cho một mảng số nguyên .
Yêu cầu: Trả về một mảng , trong đó bằng tích của tất cả các phần tử trong mảng ngoại trừ .
Giới hạn:
- Dữ liệu đảm bảo tích của tất cả các phần tử tiền tố và hậu tố của mảng đều nằm trong phạm vi số nguyên 32 bit.
- Không được sử dụng phép chia và giải quyết vấn đề trong thời gian .
- Nâng cao: Giải quyết vấn đề trong không gian phụ .
- .
- .
Ví dụ:
- Ví dụ 1:
- Ví dụ 2:
Ý tưởng giải quyết
Ý tưởng 1: Duyệt mảng hai lần
- Tạo một mảng có cùng độ dài với mảng .
- Duyệt mảng từ trái sang phải, tính tích của các phần tử bên trái và lưu vào mảng .
- Duyệt mảng từ phải sang trái, tính tích của các phần tử bên phải và nhân với giá trị ban đầu của để có kết quả cuối cùng.
Ý tưởng 1: Cài đặt
Ý tưởng 1: Phân tích độ phức tạp
- Độ phức tạp thời gian: .
- Độ phức tạp không gian: .