我需要有关基于红宝石的解决方案的建议，以解决Interviewbit上的问题。问题如下
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），因为我们只是迭代数字中的数字。那么，有人可以告诉我为什么它会超过时间限制吗？
谢谢
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)。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句