【每日一题0627】非自身以外数字的乘积

给定长度为 n 的整数列表 nums,其中 n > 1。要求返回输出列表 output ,其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

示例:

输入: [1,2,3,4]
输出: [24,12,8,6]

说明: 请 不要使用除法,且在 O(n) 时间复杂度内完成此题。

题目难度:中等
题目来源:力扣 238. 除自身以外数组的乘积

def solution(input_list):
    pass
    
assert solution([1,2,3,4]) == [24,12,8,6]
"""
给定长度为 n 的整数列表 nums,其中 n > 1。要求返回输出列表 output ,其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

示例:

输入: [1,2,3,4]
输出: [24,12,8,6]
说明: 请 不要使用除法,且在 O(n) 时间复杂度内完成此题。

题目难度:中等
题目来源:力扣 238. 除自身以外数组的乘积
"""


def solution(input_list):
    result = [1]
    # 先从下标为0乘到当前位置-1
    p = 1
    for i in range(len(input_list) - 1):  # 偏移一位
        p *= input_list[i]
        result.append(p)
    q = 1
    # 再从下标为-1乘到当前位置+1
    for j in range(len(input_list) - 1, 0, -1):  # 偏移一位
        q *= input_list[j]
        result[j - 1] *= q
    return result


assert solution([1, 2, 3, 4]) == [24, 12, 8, 6]
assert solution([1, 2]) == [2, 1]

这题确实没有思路,copy了leetcode的思路, :face_with_monocle:

给你一个长度为 n 的整数数组 nums,其中 n > 1,返回输出数组 output ,其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

除自身以外数组的乘积【参照别人写的,还是不太明白】

def solution(li):
result = [1] * (len(li))
for i in range(1, len(li)):
result[i] = result[i - 1] * li[i - 1]
q = 1
for j in reversed(range(len(li))):
result[j] *= q
q *= li[j]
print(result)
return result

class TestProductExceptMe:

def test_Product(self):
    assert solution([1, 2, 3, 4]) == [24, 12, 8, 6]

思路:

想了一天终于想通了。其实题目可以转换为,从n个数字中抽取n-1个数字的排列。因为除开自身,就跟把自身当作1来计算是一个道理。然后对排列元素进行乘积。
虽然不符leetcode范式,但也只能想到这里了。

import itertools
from functools import reduce

def solution(input_list):
    comb = itertools.combinations(input_list, 3)
    return [reduce(lambda x,y:x*y, item) for item in comb][::-1]

assert [24,12,8,6] == solution([1,2,3,4])

:partying_face: :partying_face: :partying_face: :partying_face: :partying_face: :partying_face:


写法简单易理解,不过时间复杂度上没有达标。
有大佬可以给点思路怎么修改成符合时间复杂度吗

写了个复杂的

#conding=utf-8
import copy

def solution(list_a):
    """
    给定长度为 n 的整数列表 nums,其中 n > 1。要求返回输出列表 output ,其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
    复杂度为o(n)
    """
    b=len(list_a)
    c=0
    list_b=[]

    for i in range(b):
        sum = 1
        # print(f"长度为{range(b)}")
        # print(f"循环开始第{i}次")
        #深拷贝
        a = copy.deepcopy(list_a)
        # print(f"当前list_a为{list_a}")
        # print(f"当前a为{a}")
        # print(f"准备剔除标号{i} 值为{a[i]}")
        a.remove(a[i])
        # print(a)
        for i in range(b-1):
            sum*=a[i]
            # print(f"当前循环sum的值是{sum}")
        list_b.append(sum)
        # print(f"list_b值是{list_b}")
    return list_b


if __name__ == '__main__':
    assert solution([1, 2, 3, 4]) == [24, 12, 8, 6]
    assert solution([1, 2]) == [2, 1]

抄并理解。

class Solution:
    def productExceptSelf(self, nums):
        # nums=len(list_a)
        length = len(nums)

        # L 和 R 分别表示左右两侧的乘积列表
        L, R, answer = [0] * length, [0] * length, [0] * length
        # L[i] 为索引 i 左侧所有元素的乘积
        # 对于索引为 '0' 的元素,因为左侧没有元素,所以 L[0] = 1
        L[0] = 1
        for i in range(1, length):
            L[i] = nums[i - 1] * L[i - 1]

        # R[i] 为索引 i 右侧所有元素的乘积
        # 对于索引为 'length-1' 的元素,因为右侧没有元素,所以 R[length-1] = 1
        R[length - 1] = 1
        for i in reversed(range(length - 1)):
            R[i] = nums[i + 1] * R[i + 1]

        # 对于索引 i,除 nums[i] 之外其余各元素的乘积就是左侧所有元素的乘积乘以右侧所有元素的乘积
        for i in range(length):
            answer[i] = L[i] * R[i]

        return answer



assert Solution().productExceptSelf([1, 2, 3, 4]) == [24, 12, 8, 6]
assert Solution().productExceptSelf([1, 2]) == [2, 1]
关闭