我在网上看到很多解释时间复杂度的文章,但没有找到任何好的解释空间复杂度的文章。我正在尝试解决以下面试问题
You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the Ts digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.
EXAMPLE
Input: (7-> 1 -> 6) + (5 -> 9 -> 2).That is, 617 + 295.
Output: 2 -> 1 -> 9.That is, 912.
我的解决方案如下:
private Node addLists(Node head1, Node head2) {
Node summationHead = null;
Node summationIterator = null;
int num1 = extractNumber(head1);
int num2 = extractNumber(head2);
int sum = num1 + num2;
StringBuilder strValue = new StringBuilder();
strValue.append(sum);
String value = strValue.reverse().toString();
char[] valueArray = value.toCharArray();
for (char charValue : valueArray) {
Node node = createNode(Character.getNumericValue(charValue));
if (summationHead == null) {
summationHead = node;
summationIterator = summationHead;
} else {
summationIterator.next = node;
summationIterator = node;
}
}
return summationHead;
}
private Node createNode(int value) {
Node node = new Node(value);
node.element = value;
node.next = null;
return node;
}
private int extractNumber(Node head) {
Node iterator = head;
StringBuilder strNum = new StringBuilder();
while (iterator != null) {
int value = iterator.element;
strNum.append(value);
iterator = iterator.next;
}
String reversedString = strNum.reverse().toString();
return Integer.parseInt(reversedString);
}
有人可以为此推断出空间复杂度吗?谢谢。
最佳答案
空间复杂度意味着“运行该算法所需的空间量如何随着输入变大而渐近变化”?
因此您有两个长度为 N 和 M 的列表。结果列表的长度将达到 max(N,M),如果有进位,则可能为 +1。但 +1 是一个常数,我们不认为它是 Big-O 的一部分,因为 N 或 M 中较大的一个将占主导地位。
另请注意,此算法非常简单。没有需要大于线性空间的中间计算。
空间复杂度为max(N,M)。
关于algorithm - 试图理解这个算法的空间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35324224/