Java 中的加一问题

这是一个非常有趣的问题，经常在Google、Amazon、TCS、Accenture、Adobe、Apple、Infosys等顶级IT公司的面试中出现。通过解决这个问题，可以考察应聘者的逻辑思维能力、批判性思维和问题解决能力。因此，在本节中，我们将介绍Java中“数组加一”问题的不同方法和逻辑。我们还将为此创建Java程序。

问题陈述

在这个问题中，我们给定一个数组，其中每个元素代表一个数字，整个数组代表一个数字。数字从MSB到LSB按从左到右的顺序排列。假设数字没有前导零。

任务是给数字加1，并将结果以数字数组的形式返回。

让我们通过示例来理解。

示例

输入： arr = [2, 5, 9, 7]

输出 [2, 5, 9, 8]

这代表数字 2597。在最高有效位加1，得到 2598。输出将是 [2, 5, 9, 8]。

让我们看另一个例子。

输入： arr = [9, 9]

输出 [1, 0, 0]

这代表数字 99。在最高有效位加1，得到 100。输出将是 [1, 0, 0]。

问题解决方案

朴素方法

简单的方法是先将数组转换为一个数字，然后加一，最后将结果以数组的形式返回。但这种方法不适用于大型数组。因此，我们将逐个处理每个数字。

1. 从最低有效位开始，逐个处理每个数字，直到最高有效位。
2. 如果当前数字小于9，则将当前数字加1并返回数组，否则将当前数字赋值为零。
3. 如果最后一个元素被处理，并且它也等于9，这意味着所有数字都是9。因此，我们将数组的大小增加1，并将MSB设置为1。
4. 返回结果数组。

数组加一 Java 程序

PlusOneArray.java

输出

[6, 3, 8, 3]

使用Vector

另一种方法是使用Vector。在这种方法中，我们从Vector的末尾开始。如果最后一个元素是9，将其设置为0，否则退出循环。

如果所有数字都是9，则在开头设置1，否则在循环停止的位置增加元素。注意，不需要进位、除法和模运算。

让我们在 Java 程序中实现上述方法。

PlusOneExample1.java

输出

12 45 90 35

让我们看看另一种方法。

在这种方法中，我们首先反转给定的数组。然后，使用一个进位变量来存储进位。从头开始迭代数组并加1。进位等于该索引处数组的值。

现在检查该索引处的值是否大于等于9。如果是，则将进位设置为十位数，数组中的值将是各位上的值，否则直接继续。

重复以上步骤，直到到达数组的最后一个元素。注意，如果进位不为0，则简单地在数组中加1。最后，反转数组，以便我们得到原始数组。

让我们在 Java 程序中实现上述方法。

PlusOneExample2.java

输出

1 0 0 0 0

复杂度

所有上述方法的 time complexity 都是 O(n)，因为我们只遍历了一次数组。其中 n 是数组的长度。

如果数组中至少有一个数字小于9，则该方法的 space complexity 是 O(1)，否则是 O(n)。