找出数组的串联值

标签: 数组双指针模拟

难度: Easy

给你一个下标从 0 开始的整数数组 nums 。

现定义两个数字的串联是由这两个数值串联起来形成的新数字。

例如，15 和 49 的串联是 1549 。

nums 的 串联值 最初等于 0 。执行下述操作直到 nums 变为空：

如果 nums 中存在不止一个数字，分别选中 nums 中的第一个元素和最后一个元素，将二者串联得到的值加到 nums 的 串联值 上，然后从 nums 中删除第一个和最后一个元素。
如果仅存在一个元素，则将该元素的值加到 nums 的串联值上，然后删除这个元素。

返回执行完所有操作后 nums 的串联值。

示例 1：

输入：nums = [7,52,2,4]
输出：596
解释：在执行任一步操作前，nums 为 [7,52,2,4] ，串联值为 0 。
 - 在第一步操作中：
我们选中第一个元素 7 和最后一个元素 4 。
二者的串联是 74 ，将其加到串联值上，所以串联值等于 74 。
接着我们从 nums 中移除这两个元素，所以 nums 变为 [52,2] 。
 - 在第二步操作中： 
我们选中第一个元素 52 和最后一个元素 2 。 
二者的串联是 522 ，将其加到串联值上，所以串联值等于 596 。
接着我们从 nums 中移除这两个元素，所以 nums 变为空。
由于串联值等于 596 ，所以答案就是 596 。

示例 2：

输入：nums = [5,14,13,8,12]
输出：673
解释：在执行任一步操作前，nums 为 [5,14,13,8,12] ，串联值为 0 。 
- 在第一步操作中： 
我们选中第一个元素 5 和最后一个元素 12 。 
二者的串联是 512 ，将其加到串联值上，所以串联值等于 512 。 
接着我们从 nums 中移除这两个元素，所以 nums 变为 [14,13,8] 。
- 在第二步操作中：
我们选中第一个元素 14 和最后一个元素 8 。
二者的串联是 148 ，将其加到串联值上，所以串联值等于 660 。
接着我们从 nums 中移除这两个元素，所以 nums 变为 [13] 。 
- 在第三步操作中：
nums 只有一个元素，所以我们选中 13 并将其加到串联值上，所以串联值等于 673 。
接着我们从 nums 中移除这个元素，所以 nums 变为空。 
由于串联值等于 673 ，所以答案就是 673 。

提示：

1 <= nums.length <= 1000
1 <= nums[i] <= 10⁴

Submission

运行时间: 26 ms

内存: 16.2 MB

class Solution:
    def findTheArrayConcVal(self, nums: List[int]) -> int:
        ans = 0
        i = 0
        j = len(nums) - 1
        while i < j:
            x = nums[i]
            y = nums[j]
            while y:
                x *= 10
                y //= 10
            ans += x + nums[j]
            i += 1
            j -= 1
        if i == j:
            ans += nums[i]
        return ans

Explain

该题解通过双指针的方式从数组的两端开始操作。指针i初始化在数组的开头，指针j初始化在数组的末尾。在每次循环中，首先检查两个指针是否相遇。如果没有相遇，分别取出指针i和j所指向的数组元素，计算这两个数的串联值。为了计算串联值，首先需要确定将j所指元素拼接到i所指元素后面时，需要在i元素后面添加多少个零。这是通过不断地将j元素整除10直到为0来计算。然后将得到的串联值累加到最终答案中，并将两个指针向中心移动。当两个指针相遇时，如果数组长度为奇数，则将该中心元素直接累加到结果中。这样直到数组被完全遍历完毕。

时间复杂度: O(n)

空间复杂度: O(1)

# Solution class definition
class Solution:
    def findTheArrayConcVal(self, nums: List[int]) -> int:
        ans = 0  # 初始化串联值为0
        i = 0  # 开始指针
        j = len(nums) - 1  # 结束指针
        while i < j:  # 当开始和结束指针未相遇时
            x = nums[i]  # 获取开始指针的值
            y = nums[j]  # 获取结束指针的值
            # 将y的每一位数加到x的后面
            while y:  
                x *= 10
                y //= 10
            ans += x + nums[j]  # 计算当前的串联值并累加
            i += 1  # 移动开始指针
            j -= 1  # 移动结束指针
        if i == j:  # 如果中间还剩一个元素
            ans += nums[i]  # 直接加到串联值上
        return ans  # 返回最终的串联值

Explore

在进行数字的串联操作时，我们需要保证j元素整体排列在i元素的后面。为了实现这一点，在不使用字符串操作的情况下，我们必须了解j元素的位数，以便可以通过乘以相应的10的幂将i元素扩展到足够大，从而在不改变其原始数值的情况下，将j元素附加在其后。例如，如果i是123，j是4567，则i需要扩展为1230000后，再加上4567，得到最终的串联结果1234567。这种方法是数学上处理数字串联的直接方式。

在这个算法中，当数组的元素个数为奇数时，最中间的元素被直接加到最终结果中，这是因为该元素没有与之配对的元素来形成串联值。这种处理方式是合理的，因为每个元素都应该被考虑在内。对于中间的元素，由于没有可以与之配对的另一个元素，所以其本身直接被加入最终结果是正确的处理方式，这不会错误地影响最终的串联值，而是确保了所有元素都被恰当地考虑了。

该算法在设计时已经考虑了包括数组只有一个元素的情况在内的各种边界条件。当数组只有一个元素时，由于i和j初始指向同一位置（i = 0, j = 0），循环条件i < j不满足，因此循环不会执行，直接跳至检查i == j的条件。因为这里i等于j，所以单一元素直接被加入到最终的串联值中，正确处理了只有一个元素的情况。

双指针方法在这个问题中效率较高，主要是因为它可以在单次遍历中处理完所有元素的串联。与递归方法相比，双指针避免了额外的调用栈开销，并且通常更易于理解和实现。与单循环相比，双指针方法可以更直观地在每次迭代中处理两个元素的串联，减少了可能的重复计算。总体而言，双指针方法在空间和时间效率上通常优于递归，并且在实现上比单循环更直观有效。