2578. 最小和分割

难度: 简单

来源: 每日一题 2023.10.09

---

给你一个正整数 num ，请你将它分割成两个非负整数 num1 和 num2 ，满足：

• num1 和 num2 直接连起来，得到 num 各数位的一个排列。

  • 换句话说，num1 和 num2 中所有数字出现的次数之和等于 num 中所有数字出现的次数。

• num1 和 num2 可以包含前导 0 。

请你返回 num1 和 num2 可以得到的和的 最小 值。

注意：

• num 保证没有前导 0 。
• num1 和 num2 中数位顺序可以与 num 中数位顺序不同。

示例 1：

输入：num = 4325
输出：59
解释：我们可以将 4325 分割成 num1 = 24 和 num2 = 35 ，和为 59 ，59 是最小和。

示例 2：

输入：num = 687
输出：75
解释：我们可以将 687 分割成 num1 = 68 和 num2 = 7 ，和为最优值 75 。

提示：

• 10 <= num <= 10^9

class Solution {
    public int splitNum(int num) {

    }
}

分析与题解

---

• 贪心算法

  这个题的思路是这样的, 要想把 num 分成和最小的两个数. 那么根据尝试一定要有以下的规律.

  • 两个拆分数字 num1 和 num2 位数尽量相同

    • 例如 11111111 拆分为 1111 ➕ 1111 ,正确拆分

    • 11111111 拆分为 11111 ➕ 111 ,错误拆分

  • num 切割分成两堆数字 array1 和 array2, 同时保证两堆组成的数字之和最小, 那么分配规则一定是 最小数字 → array1 最小数字 → array2 最大数字 → array1 最大数字 → array2 这样的顺序才能保证两堆组成的数字之和最小.

  • 给定一些数字, 要组成一个最小的数字. 一定是最小的数字在高位, 最大的数字在低位.

    • 例如 1 3 7 5, 组成的最小的数字为 1357

  基于上面的理论, 我们首先尝试把 num 拆分成数组, 并且进行排列.

  

  List<Integer> numArray = new ArrayList<>();
  while(num != 0) {
      int oneNum = num%10;
      num = num/10;
      numArray.add(oneNum);
  }
  Collections.sort(numArray);
  

  然后, 我们利用双指针尽量把数组平分拆分成两个数组 num1Array 和 num2Array. 规则则按照 最小数字 → array1 最小数字 → array2 最大数字 → array1 最大数字 → array2 这样的顺序.

  

  List<Integer> num1Array = new ArrayList<>();
  List<Integer> num2Array = new ArrayList<>();
  int left = 0;
  int right = numArray.size() - 1;
  while(left <= right) {
      num1Array.add(numArray.get(left));
      left++;
      if (left <= right) {
          num2Array.add(numArray.get(left));
          left++;
      }
      if (left <= right) {
          num1Array.add(numArray.get(right));
          right--;
      }
      if (left <= right) {
          num2Array.add(numArray.get(right));
          right--;
      }
  }
  

  然后, 我们需要对两堆数组进行排序, 然后组装成数字即可.

  String num1String = "0";
  String num2String = "0";
  Collections.sort(num1Array);
  Collections.sort(num2Array);
  
  for(int i : num1Array) {
      num1String += i;
  }
  for(int i : num2Array) {
      num2String += i;
  }
  

  最后输出最后的结果即可.

  return Integer.valueOf(num1String) + Integer.valueOf(num2String);
  

  我们一起看一下当时的解题过程.

  class Solution {
      public int splitNum(int num) {
          // 分割成数组,排序 按照 小小 → 大大 的顺序取值即可
          List<Integer> numArray = new ArrayList<>();
          List<Integer> num1Array = new ArrayList<>();
          List<Integer> num2Array = new ArrayList<>();
          String num1String = "0";
          String num2String = "0";
          while(num != 0) {
              int oneNum = num%10;
              num = num/10;
              numArray.add(oneNum);
          }
          Collections.sort(numArray);
          int left = 0;
          int right = numArray.size() - 1;
          while(left <= right) {
              num1Array.add(numArray.get(left));
              left++;
              if (left <= right) {
                  num2Array.add(numArray.get(left));
                  left++;
              }
              if (left <= right) {
                  num1Array.add(numArray.get(right));
                  right--;
              }
              if (left <= right) {
                  num2Array.add(numArray.get(right));
                  right--;
              }
          }
          Collections.sort(num1Array);
          Collections.sort(num2Array);
  
          for(int i : num1Array) {
              num1String += i;
          }
          for(int i : num2Array) {
              num2String += i;
          }
          return Integer.valueOf(num1String) + Integer.valueOf(num2String);
      }
  }
  

  复杂度分析:

  • 时间复杂度: O(4n), 4次遍历, 整体是线性的时间复杂度.
  • 空间复杂度: O(3n), 需要创建3个与数字位数成线性关系的内存空间.

  结果如下所示.

  

• 贪心算法 (官方解法)

  整体思路和我上面的是一样的, 不过官方的遍历的思路是一遍遍历, 交替赋值. 那么也不需要上面后期对两堆数字进行排序的操作了. 减少了时间复杂度.

  • 将 num 的数字进行递增排序；

    char[] numArray = Integer.toString(num).toCharArray();
    Arrays.sort(numArray);
    

  • 按照递增顺序，交替地将数字分配给 num1 和 num2

    int num1 = 0;
    int num2 = 0;
    for(int i = 0; i < numArray.length; i++) {
        if (i%2 == 0) {
            num1 = num1 * 10 + (numArray[i] - '0');
        } else {
            num2 = num2 * 10 + (numArray[i] - '0');
        }
    }
    

  我们一起看一下具体的解题过程.

  class Solution {
      public int splitNum(int num) {
          char[] numArray = Integer.toString(num).toCharArray();
          Arrays.sort(numArray);
          int num1 = 0;
          int num2 = 0;
          for(int i = 0; i < numArray.length; i++) {
              if (i%2 == 0) {
                  num1 = num1 * 10 + (numArray[i] - '0');
              } else {
                  num2 = num2 * 10 + (numArray[i] - '0');
              }
          }
          return num1 + num2;
      }
  }
  

  复杂度分析:

  • 时间复杂度: O(n), 一次遍历, 整体是线性的时间复杂度.
  • 空间复杂度: O(n), 需要创建1个与数字位数成线性关系的内存空间.

  结果如下所示.