您有一个整数数组，对于每个索引，您想要找到除该索引处的整数之外的每个整数的乘积

Question

我正在研究一些面试问题，并在一个网站上看到了这个问题。我在 Ruby 中提出了一个解决方案，我想知道它是否有效且可以接受。我已经编码一段时间了，但以前从未关注过解决方案的复杂性。现在我正在努力学习如何最大限度地减少时间和 space 复杂性。

问题： 您有一个整数数组，对于每个索引，您想要找到除该索引处的整数之外的每个整数的乘积。

示例：

arr = [1,2,4,5]
result = [40, 20, 10, 8]

# result = [2*4*5, 1*4*5, 1*2*5, 1*2*4]

考虑到这一点，我想到了这个解决方案。

解法：

def find_products(input_array)
    product_array = []
    input_array.length.times do |iteration|
        a = input_array.shift
        product_array << input_array.inject(:*)
        input_array << a
    end
    product_array
end

arr = find_products([1,7,98,4])

据我了解，我访问数组的次数与其长度一样多，这在效率和速度方面被认为是糟糕的。我仍然不确定我的解决方案有多复杂。

感谢任何有助于提高效率的帮助，如果您还可以告诉我解决方案的复杂性以及如何计算它，那就更好了。

谢谢

Answer 1

def product_of_others(arr)
  case arr.count(0)
  when 0
    total = arr.reduce(1,:*)
    arr.map { |n| total/n }
  when 1
    ndx_of_0 = arr.index(0)
    arr.map.with_index do |n,i|
      if i==ndx_of_0
        arr[0,ndx_of_0].reduce(1,:*) * arr[ndx_of_0+1..-1].reduce(1,:*)
      else
        0
      end
    end
  else
    arr.map { 0 }
  end
end

product_of_others [1,2,4,5]  #=> [40, 20, 10, 8]
product_of_others [1,-2,0,5] #=> [0, 0, -10, 0]
product_of_others [0,-2,4,5] #=> [-40, 0, 0, 0] 
product_of_others [1,-2,4,0] #=> [0, 0, 0, -8]
product_of_others [1,0,4,0]  #=> [0, 0, 0, 0]
product_of_others []         #=> []

对于 arr 不包含零的情况，我使用 arr.reduce(1,:*) 而不是 arr.reduce(:*) 以防数组为空。同样，如果 arr 包含一个零，我使用 .reduce(1,:*) 以防零位于数组的开头或结尾。

Answer 2

我不知道ruby，但是，访问一个数组是O(1)，也就是说是常数时间，所以你的算法复杂度是O(n)，很好。我不认为在复杂性方面可以找到更好的解决方案。实际速度是另一个问题，但这个解决方案很好

Answer 3

对于不包含零的输入（对于其他，见下文）

对我来说最简单（也相对有效）的似乎是首先得到总积：

total_product = array.inject(1){|product, number| product * number}

然后将每个数组元素映射到total_product除以元素：

result = array.map {|number| total_product / number}

初始计算 total_product = 1*2*4*5 后，将计算

result = [40/1, 40/2, 40/4, 40/5]

据我所知，总计为 O(n) [创建总产品：触摸每个数字一次] + O(n) [为每个数字创建一个结果：触摸每个数字一次]。（如有错误请指正）

更新

正如@hirolau 和@CarySwoveland 指出的那样，如果输入中有（恰好 1 个）0，就会出现问题，因此：

对于包含零的输入（解决方法，但借用了性能优势和复杂性 class）

zero_count = array.count{|number| number == 0}
if zero_count == 0
  # as before
elsif zero_count == 1
  # one zero in input, result will only have 1 non-zero
  nonzero_array = array.reject{|n| n == 0}
  total_product = nonzero_array.inject(1){|product, number| product * number}
  result = array.map do |number|
    (number == 0) ? total_product : 0
  end
else
  # more than one zero? All products will be zero!
  result = array.map{|_| 0}
end

抱歉，这个答案现在基本上等于@CarySwoveland，但我认为我的代码更明确。查看有关进一步性能考虑的评论。

Answer 4

我会这样做：

arr = [1,2,4,5]

result = arr.map do |x|
  new_array = arr.dup  # Create a copy of original array
  new_array.delete_at(arr.index(x)) # Remove an instance of the current value
  new_array.inject(:*) # Return the product.
end

p result  # => [40, 20, 10, 8]

您有一个整数数组，对于每个索引，您想要找到除该索引处的整数之外的每个整数的乘积

You have an array of integers, and for each index you want to find the product of every integer except the integer at that index

arrays

ruby

big-o

complexity-theory

greedy

对于不包含零的输入（对于其他，见下文）

对于包含零的输入（解决方法，但借用了性能优势和复杂性 class）