Tích mảng ngoại trừ chính nó (Product of Array Except Self) trong Python

Giả sử chúng ta có mảng nums chứa n số nguyên với n > 1. Chúng ta phải tìm mảng output sao cho output[i] bằng tích của tất cả các phần tử của nums trừ nums[i]. Ví dụ, nếu mảng đầu vào là [1,2,3,4], đầu ra sẽ là [24,12,8,6]. Chúng ta phải giải quyết không sử dụng phép chia.

Để giải quyết, chúng ta làm theo các bước sau:

• Tạo mảng tich_phai cùng kích thước nums, điền 0.

• Phần tử cuối của tich_phai = phần tử cuối của nums.

• Với i từ 1 đến độ dài nums:

  • tich_phai[do_dai - i - 1] = tich_phai[do_dai - i] * nums[do_dai - i - 1].

• Tạo mảng ket_qua cùng kích thước nums, điền 0.

• Tiền tố prefix := 1, chỉ số chi_so := 0.

• Khi chi_so < độ dài ket_qua - 1:

  • ket_qua[chi_so] := prefix * tich_phai[chi_so + 1].
  • prefix := prefix * nums[chi_so].
  • chi_so := chi_so + 1.

• Phần tử cuối của ket_qua := prefix.

• Trả về ket_qua.

Ví dụ

class Solution(object):
    def productExceptSelf(self, nums):
        tich_phai = [0] * len(nums)
        tich_phai[-1] = nums[-1]
        for i in range(1, len(nums)):
            tich_phai[len(nums)-i-1] = tich_phai[len(nums)-i] * nums[len(nums)-i-1]
        ket_qua = [0] * len(nums)
        tien_to = 1
        chi_so_hien_tai = 0
        while chi_so_hien_tai < len(ket_qua) - 1:
            ket_qua[chi_so_hien_tai] = tien_to * tich_phai[chi_so_hien_tai + 1]
            tien_to *= nums[chi_so_hien_tai]
            chi_so_hien_tai += 1
        ket_qua[-1] = tien_to
        return ket_qua

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]