将表示数字的数组加一

问题陈述

给定一个由 0 到 9 的数字组成的数组，该数组表示一个数字。数组的第一个元素代表数字的最高有效位，最后一个元素代表最低有效位。

由于该数字是非负数，因此不需要额外的符号位（因为默认情况下，非负数不需要额外的符号位）。

我们的目标是将此数字加 1 并将其存储在数组中，或者说，我们必须将数组表示的数字加一。

例如

在上面的示例中，数组表示数字 5864947，我们加了 1，现在值为 5864948，它以数组的形式表示。

假设我们最初有 n 位数字，则它将由数组中的 n 个元素表示。在最坏的情况下，结果数组将包含 n + 1 个元素。

例如

在上面的示例中，数组中有四个元素，它们表示数字 9999。如果我们加 1，我们的数字将等于 10000，它由五个元素表示。

方法 1

解决此问题的第一个方法是将数组表示的数字转换为整数。然后我们将 1 加到该数字上，并将结果整数转换为数组。

Java 代码

输出

说明

在上面的代码中，我们有一个表示数字的数组，并且有两个函数。

一个函数使用除法方法返回数组的等效数字。然后，在获得等效数字后，我们将数字加 1。现在我们使用第二个函数将这个 num 转换为数组。

在第二个函数中，我们首先计算我们数字中的位数，然后将数组大小声明为与数字的位数相同。然后我们使用除法方法将每个数字填充到数组中。

因此，如果 n 表示数组中的元素数量，则时间复杂度将为：O(n)，空间复杂度也将为：O(n)。

方法 2

与将数组转换为数字然后再将其转换回数组相比，我们可以直接在数组上进行操作。

但是，这里结果数组的大小可能会增加一个，因此我们将使用 ArrayList 而不是数组来动态调整大小。

Java 代码

输出

说明

在上面的代码中，我们有一个表示数字的数组。我们将使用额外的变量来维护进位。最初，进位为零，我们将使用 ArrayList 来存储结果值。

我们将从数组的末尾开始到开头，因为我们将从最低有效位到最高有效位进行加法运算。

由于我们必须将原始数字加 1，我们将进位和 1 加到数组的最后一个元素。如果该值大于 9，那么我们将通过对十取模来转换该值，进位将为 1。对于所有其他元素，我们将进位加到该特定元素上，并将进位传递到左侧的下一个数字。

最后，如果进位为 1，那么我们将 1 添加到结果 ArrayList 的第 0 个索引。否则，我们不会。

因此，通过这种方法，我们将得到 ArrayList 中的等效数字。

所以时间复杂度将是 O(n)，其中 n 是数组中的元素数量。

空间复杂度将是 O(n)，用于将结果存储在 ArrayList 中。