arrays - 在 ruby​​ 中实现的算法将 1 添加到表示为数组的数字

Question

我需要有关 Interviewbit 上的问题的基于 ruby​​ 的解决方案的建议。问题如下

Given a non-negative number represented as an array of digits,

add 1 to the number ( increment the number represented by the digits ).

The digits are stored such that the most significant digit is at the head of the list. There can be upto 10,000 digits in the input array.

Example:

If the vector has [1, 2, 3]

the returned vector should be [1, 2, 4]

as 123 + 1 = 124. 

我的第一个解决方案如下

 def plusOne(a)
        new_number = a.join.to_i + 1
        result = []
        while new_number > 0
            result.push new_number%10
            new_number /= 10
        end
        result.reverse
 end

该算法似乎是正确的，它通过了测试输入，但在提交时给出了“超出时间限制”。我的第二个解决方案提交成功，如下。

def plusOne(a)
      carry = 1
      start_index = a.size - 1
      temp_result = []
      ans = []

      for i in start_index.downto(0)
            sum = a[i] + carry
            carry = sum/10
            temp_result.push sum%10
      end
      temp_result.push carry

      start_index = temp_result.size - 1
      while start_index >= 0 and temp_result[start_index] == 0
          start_index -= 1
      end

      while start_index >= 0
          ans.push temp_result[start_index]
          start_index -= 1
      end
      ans
    end

我的第一个解决方案对我来说似乎是 O(n)，因为我们只是迭代数字中的数字。那么，有人可以告诉我为什么它会超过时间限制吗？

谢谢

Answer 1

while new_number > 0
    result.push new_number%10
    new_number /= 10
end

虽然乍一看这个循环似乎是 O(n)，但它至少是 Ω(n²)。

由于 Ruby 中的大数字是作为二进制数字数组(基数为 2³² 的数字)存储和处理的，因此除以 10 是一项代价高昂的操作。确切的时间复杂度取决于 Ruby 使用的除法算法，但是 new_number/= 10 必须处理所有 new_number 的二进制数字，所以它不能比O(n)。