Cho một mảng các số nguyên nums. Hãy trả về một mảng answer sao cho answer[i] đúng bằng tích của tất cả các phần tử trong nums ngoại trừ nums[i].
Yêu cầu bắt buộc: Bạn phải thiết kế thuật toán chạy trong thời gian O(n) và TUYỆT ĐỐI KHÔNG được sử dụng phép chia.
Ví dụ 1:
Input: nums = [1, 2, 3, 4]
Output: [24, 12, 8, 6]
Giải thích:
answer[0] = 2 * 3 * 4 = 24
answer[1] = 1 * 3 * 4 = 12
answer[2] = 1 * 2 * 4 = 8
answer[3] = 1 * 2 * 3 = 6Ví dụ 2:
Input: nums = [-1, 1, 0, -3, 3]
Output: [0, 0, 9, 0, 0]Định Dạng Đầu Vào (Input)
Một dòng chứa mảng số nguyên nums
Định Dạng Đầu Ra (Output)
Mảng kết quả answer có cùng độ dài
Ràng Buộc (Constraints)
2 <= nums.length <= 10^5-30 <= nums[i] <= 30
Ví Dụ Kiểm Thử Mẫu
Ví dụ 1:
Input:
[1, 2, 3, 4]
Output:
[24, 12, 8, 6]
Giải thích: Tích các phần tử trừ chính nó
Ví dụ 2:
Input:
[-1, 1, 0, -3, 3]
Output:
[0, 0, 9, 0, 0]
Giải thích: Có chứa số 0
Gợi ý được sắp xếp theo cấp độ tiến dần. Hãy mở từng gợi ý khi bạn thực sự cần thêm định hướng.
Kỹ thuật Tiền Tố (Prefix) & Hậu Tố (Suffix) O(n)
Mỗi phần tử answer[i] = (tích tất cả các số bên trái i) * (tích tất cả các số bên phải i).
Quét lượt 1 từ trái sang phải tính prefix product. Quét lượt 2 từ phải sang trái nhân dồn suffix product trực tiếp vào mảng kết quả.
Dữ liệu đầu vào (Input):
[1, 2, 3, 4]
Kết quả kỳ vọng (Expected Output):
[24, 12, 8, 6]
Dữ liệu đầu vào (Input):
[-1, 1, 0, -3, 3]
Kết quả kỳ vọng (Expected Output):
[0, 0, 9, 0, 0]
Nhập STDIN của bạn (Mỗi dòng một tham số):
Bấm Chạy thử để kiểm tra các bộ test mẫu hoặc Nộp bài để chấm điểm chính thức.
Đang gửi mã và thực thi trên Sandbox Engine...
