2562. 找出数组的串联值

2562. 找出数组的串联值

难度: 简单

来源: 每日一题 2023.10.12

---

给你一个下标从 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 。
1
2
3
4
5
6
7
8
9
10
11
12

示例 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15

提示：

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 10^4

class Solution {
    public long findTheArrayConcVal(int[] nums) {

    }
}
1
2
3
4
5

分析与题解

---

• 双指针移动 + 模拟法

  定义一个双指针, 然后从数组的左右两边往中间移动, 一共会有三种情况.

  • 当 left < right 时, 进行串联操作.

    String numString = "" + nums[left] + nums[right];
    result += Integer.valueOf(numString);
    1
    2

  • 当 left = right 时, 直接添加当前的元素.

    result += nums[left];
    1

  • 当 left > right 时, 停止遍历操作.

    while(left <= right) {
        ...
    }
    1
    2
    3

  接下来, 我们一起看一下整体的实现逻辑, 具体代码如下所示.

  class Solution {
      public long findTheArrayConcVal(int[] nums) {
          int left = 0, right = nums.length - 1;
          long result = 0;
          while(left <= right) {
              if(left == right) {
                  result += nums[left];
              } else {
                  String numString = "" + nums[left] + nums[right];
                  result += Integer.valueOf(numString);
              }
              left++;
              right--;
          }
          return result;
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17

  复杂度分析:

  • 时间复杂度: O(nlogU), 一次遍历循环, 时间复杂度与数组长度成线性相关. U表示每一个数字的位数, 转换成字符串的时间复杂度为logU
  • 空间复杂度: O(logU), 数字转字符串的时候需要的空间复杂度为logU.

  结果如下所示.

  

• 双指针移动 + 模拟法 (优化)

  由于数字转字符串的时间消耗过长, 所以这里写一个函数, 计算 a , b 两者的 串联值 . 方法也很简单, 这里就不过多叙述了.

  public long twoNumsSumResult(int a, int b) {
      int times = 0;
      int end = b;
      while (end > 0) {
          end /= 10;
          times++;
      }
      return a * (long)Math.pow(10, times) + b;
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9

  接下来, 我们一起看一下整体的实现逻辑, 具体代码如下所示.

  class Solution {
      public long findTheArrayConcVal(int[] nums) {
          int left = 0, right = nums.length - 1;
          long result = 0;
          while(left <= right) {
              if(left == right) {
                  result += nums[left];
              } else {
                  result += twoNumsSumResult(nums[left], nums[right]);
              }
              left++;
              right--;
          }
          return result;
      }
      public long twoNumsSumResult(int a, int b) {
          int times = 0;
          int end = b;
          while (end > 0) {
              end /= 10;
              times++;
          }
          return a * (long)Math.pow(10, times) + b;
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25

  复杂度分析:

  • 时间复杂度: O(nU), 一次遍历循环, 时间复杂度与数组长度成线性相关. U表示每一个数字的位数, 对于 b 来说, 需要遍历来确认 位数 .
  • 空间复杂度: O(n), 确认 b 的位数时, 需要创建临时变量.

  结果如下所示.