Giả sử chúng ta có một mảng được gọi là nums của n số nguyên trong đó n> 1. Chúng ta phải tìm một đầu ra của mảng sao cho đầu ra [i] bằng tích của tất cả các phần tử của num trừ nums [i]. Vì vậy, nếu mảng đầu vào là [1,2,3,4], thì đầu ra sẽ là [24,12,8,6]. Chúng ta phải giải quyết vấn đề này mà không sử dụng toán tử phân chia.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- right_mul:=một mảng có kích thước giống như nums, điền nó bằng 0
- phần tử cuối cùng của right_mul =phần tử cuối cùng của nums
- cho tôi trong phạm vi từ 1 đến độ dài là nums
- right_mul [length of nums - i - 1] =right_mul [length of nums - i] * nums [length of nums - i - 1]
- output:=một mảng có kích thước giống như nums, điền nó bằng 0
- tiền tố:=1 và chỉ mục:=0
- while chỉ mục <độ dài của đầu ra - 1
- output [index]:=prefix * right_mul [index + 1]
- prefix:=prefix * nums [index]
- index:=index + 1
- phần tử cuối cùng của đầu ra:=prefix
- trả về kết quả đầu ra
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
class Solution(object): def productExceptSelf(self, nums): right_multiply = [0] * len(nums) right_multiply[-1]=nums[-1] for i in range(1,len(nums)): right_multiply[len(nums)-i-1] = right_multiply[len(nums)-i] * nums[len(nums)-i-1] output = [0]*len(nums) prefix = 1 current_index = 0 while current_index < len(output)-1: output[current_index] = prefix * right_multiply[current_index+1] prefix *= nums[current_index] current_index +=1 output[-1] = prefix return output ob1 = Solution() print(ob1.productExceptSelf([1,3,5,7,9]))
Đầu vào
[1,3,5,7,9]
Đầu ra
[945, 315, 189, 135, 105]