(A卷,200分)- 组合出合法最小数（Java & JS & Python）

题目描述

给一个数组，数组里面哦都是代表非负整数的字符串，将数组里所有的数值排列组合拼接起来组成一个数字，输出拼接成的最小的数字。

输入描述

一个数组，数组不为空，数组里面都是代表非负整数的字符串，可以是0开头，例如：["13", "045", "09", "56"]。

数组的大小范围：[1, 50]

数组中每个元素的长度范围：[1, 30]

输出描述

以字符串的格式输出一个数字，

• 如果最终结果是多位数字，要优先选择输出不是“0”开头的最小数字
• 如果拼接出来的数字都是“0”开头，则选取值最小的，并且把开头部分的“0”都去掉再输出
• 如果是单位数“0”，可以直接输出“0”

用例

题目解析

一般来说，如果数组中元素长度都相同的话，则可以直接将数组进行字典序升序，这样数组元素按顺序拼接得到的组合数就是最小，比如数组[45, 32, 11, 31] 按照字典序升序后变为 [11, 31, 32, 45]，然后进行拼接，得到的组合数为11313245就是最小的。

但是，如果数组中元素长度不全相同的话，则此时直接字典序升序，可能无法得到最小组合数，比如数组 [3, 32, 321]，按照字典序升序后变为 [3, 32, 321]，然后进行拼接，得到组合数332321，但是这个组合数显然不是最小的，最小的组合数应该是 321323。

而本题数组元素的长度是有可能不一样的，此时我们应该采用另一种排序规则：

即直接尝试对要组合的两个字符串a，b进行组合，此时有两种组合方式：

1. a + b
2. b + a

然后，比较 (a + b) 和 （b+a）的数值谁小，如果a+b的数值更小，则保持当前a,b顺序不变，如果b+a的数值更小，则交换a,b位置。

比如 strs = [a, b]， a = "3"，b = "32"

a + b = "332"

b + a = "323"

可以发现 b+a更小，因此交换a,b位置，strs变为[32, 3]，然后进行元素拼接得到 323 最小组合数。

另外，本题，还有其他限定规则：

• 如果最终结果是多位数字，要优先选择输出不是“0”开头的最小数字
• 如果拼接出来的数字都是“0”开头，则选取值最小的，并且把开头部分的“0”都去掉再输出

即排序后，数组开头元素如果以“0”开头，此时分两种情况讨论：

• 数组全部元素都是以“0”开头，则此时应该将拼接后的组合数去除前导0
• 数组有不以“0”开头的元素，则此时不应该把“0”开头的元素放在数组头部。

我的解题思路如下：

首先，按照前面的规则将数组元素排序，排序后，检查数组头元素是否以“0”开头，如果是的话，则开始遍历数组后面的元素，直到找到一个不以“0”开头的元素x，然后将元素x取出，并插入到数组头部。如果一直找不到这样的x，则说明数组元素全部是以0开头的，此时直接拼接出组合数，然后去除前导0。

关于去除前导0，这里不建议使用parseInt，或者python的int，因为对应组合数非常有可能超出int范围，这里我们应该保持组合数为字符串，实现去除前导0。

对于Java,JS而言，可以是正则表达式 /^0+/ 来替换前导0为空字串。

对于Python而言，可以使用lstrip方法来去除左边0

2023.03.28

本题有网友给出了一个用例：

010 02 201 20

该用例的正确答案应该是：2001002201

但是我的算法代码输出是：2010100220

因此我的算法是有问题的。

但是，我看了该题的机试系统中也有一个类似的用例：

20 02 2010 2032 698 6982 6987 0120

因此，当前我的代码是符合机试系统要求的。

为什么会这样呢？

我的猜测是，出本题的人应该是参考了leetcode的

上面这道题的策略其实就是当前我的代码算法策略。

只是出题人想搞点新花样，就是在leetcode这题的基础上允许带前导0的元素数字，结果把自己绕进去了。

有问题，但是应该可以满分的解法

JavaScript算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on("line", (line) => {
  const strs = line.split(" ");
  console.log(getResult(strs));
});

function getResult(strs) {
  strs.sort((a, b) => {
    const s1 = a + b;
    const s2 = b + a;
    return s1 == s2 ? 0 : s1 > s2 ? 1 : -1;
  });

  if (strs[0][0] == "0") {
    for (let i = 1; i < strs.length; i++) {
      if (strs[i][0] != "0") {
        strs[0] = strs[i] + strs[0];
        strs[i] = "";
        break;
      }
    }
  }

  const ans = strs.join("").replace(/^0+/, "");

  return ans == "" ? "0" : ans;
}

Java算法源码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    String[] strs = sc.nextLine().split(" ");
    System.out.println(getResult(strs));
  }

  public static String getResult(String[] strs) {
    Arrays.sort(strs, (a, b) -> (a + b).compareTo(b + a));

    if (strs[0].charAt(0) == '0') {
      for (int i = 1; i < strs.length; i++) {
        if (strs[i].charAt(0) != '0') {
          strs[0] = strs[i] + strs[0];
          strs[i] = "";
          break;
        }
      }
    }

    StringBuilder sb = new StringBuilder();
    for (String str : strs) {
      sb.append(str);
    }

    String ans = sb.toString().replaceAll("^0+", "");

    // 避免返回空串
    return "".equals(ans) ? "0" : ans;
  }
}

Python算法源码

import functools

# 输入获取
strs = input().split()


# 算法入口
def cmp(a, b):
    s1 = a + b
    s2 = b + a
    return 0 if s1 == s2 else 1 if s1 > s2 else -1


def getResult(strs):
    strs.sort(key=functools.cmp_to_key(cmp))

    if strs[0][0] == '0':
        for i in range(1, len(strs)):
            if strs[i][0] != '0':
                strs[0] = strs[i] + strs[0]
                strs[i] = ""
                break

    ans = "".join(strs).lstrip("0")

    # 避免返回空串
    return "0" if ans == "" else ans


# 算法调用
print(getResult(strs))

最优的，正确的，不超时的解法

其实本题如果想组合出最小数，有一个规律：

所有含前导的0的数必须要拼接在一起

比如用例：010 02 201 20，对应的组合最小数是：2001002201

比如用例：20 02 2010 2032 698 6982 6987 0120，对应的组合最小数是：200120022010203269826986987

有了这个规则，其实本题的求解就非常容易了。

我们可以将所有含前导0的数先筛出来，然后基于 a + b > b + a 的排序规则，求出这些含前导0的数能组合出的最小数combineZeroLead。

接着，再把所有不含前导0的数筛出来，进行字典序排序，将字典序最小的不含前导0的数选出，作为最终组合数的头部head。

剩余的不含前导0的数，继续a + b > b + a 的排序规则，求出一个最小数组合tail。

最终 head + combineZeroLead + tail 就是整体的组合最小数。

但是上面逻辑，是在既又含前导0数，又有不含前导0数的情况下。

如果输入的数：

• 全部都是不含前导0的，则直接a + b > b + a 的排序后，组合在一起返回。
• 全部都是含前导0的，则直接将combineZeroLead去除左侧0后返回，注意不能返回空串。

2023.03.29

经网友指出，上面逻辑还是有问题，比如用例：

1 0101 101

下面代码会输出结果：10101101

但是实际正确结果是：10101011

问题就在于组合数的开头head的确定，受到head + combineZeroLead的长度影响。如上面标注的绿色 + 红色。

因为head + combineZeroLead长度无法保证一致，因此我们无法简单的通过head + combineZeroLead的字典序大小，来确定head。

因此，我们需要对上面算法进行改正。

我的策略是：

将组合数分为三部分来看：head , combineZeroLead，tail

其中combineZeroLead就是含前导0的数的最小组合，这个策略和之前一样。

其次是head，head由于无法直接确定是某个数，但是可以确实是某些数，比如用例

20 02 2010 2032 698 6987 0120

head数必然只能是20 2010 2032这三个数中选，即不含0的数中，首位字典序最小的这些数。

我们可以依次遍历20 2010 2032每一个数做head，那么没有被选择的其他数就只能加到tail中。

比如，我们选择20作为head，则此时组成tail的数包括：2010,2032,698,6987

接下来，我们只要让tail组合出最小数即可，同样按照a + b > b + a的规则来排序。

这样每一种head，都有一个对应的最小数组合head + combineZeroLead + tail，我们保留其中最小的，就是题解。

Java算法源码

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    String[] nums = sc.nextLine().split(" ");
    System.out.println(getResult(nums));
  }

  public static String getResult(String[] nums) {
    // zeroLead记录含前导0的数
    ArrayList<String> zeroLead = new ArrayList<>();
    // notZeroLead记录不含前导0的数
    ArrayList<String> notZeroLead = new ArrayList<>();

    for (String num : nums) {
      if (num.charAt(0) == '0') {
        zeroLead.add(num);
      } else {
        notZeroLead.add(num);
      }
    }

    // 要使最终的组合数最小，则含前导0的数必须要组合在一起，且按照 a + b > b + a的规则排序
    if (zeroLead.size() != 0) {
      zeroLead.sort((a, b) -> (a + b).compareTo(b + a));
    }

    StringBuilder combineZeroLead = new StringBuilder();
    for (String s : zeroLead) combineZeroLead.append(s);

    // 如果输入的数都是含前导0的，则直接返回combineZeroLead，需要去除左侧0，但是注意不能返回空串
    if (notZeroLead.size() == 0) {
      String tmp = combineZeroLead.toString().replaceAll("^0+", "");
      return tmp.length() == 0 ? "0" : tmp;
    }

    //  将不含前导0的所有数进行字典序排序，将首位字典序最小的数都提取到heads中，他们都是head的可选值
    notZeroLead.sort((a, b) -> a.compareTo(b));

    ArrayList<String> heads = new ArrayList<>();
    heads.add(notZeroLead.remove(0));

    while (notZeroLead.size() > 0 && heads.get(0).charAt(0) == notZeroLead.get(0).charAt(0)) {
      heads.add(notZeroLead.remove(0));
    }

    String ans = null;
    for (int i = 0; i < heads.size(); i++) {
      // 选取某个head
      String head = heads.get(i);

      // 则heads剩下的数以及notZeroLead剩下的数将组成tail，依旧按照 a + b > b + a的规则排序，这样tail才能最小
      ArrayList<String> tail = new ArrayList<>();
      tail.addAll(notZeroLead);
      tail.addAll(heads.subList(0, i));
      tail.addAll(heads.subList(i + 1, heads.size()));

      tail.sort((a, b) -> (a + b).compareTo(b + a));

      StringBuilder tailStr = new StringBuilder();
      for (String s : tail) tailStr.append(s);

      // 最终只记录整体最小数
      if (ans != null) {
        String tmp = head + combineZeroLead + tailStr;
        if (tmp.compareTo(ans) < 0) {
          ans = tmp;
        }
      } else {
        ans = head + combineZeroLead + tailStr;
      }
    }

    return ans;
  }
}

JavaScript算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on("line", (line) => {
  const nums = line.split(" ");
  console.log(getResult(nums));
});

function getResult(nums) {
  // zeroLead记录含前导0的数
  const zeroLead = [];
  // notZeroLead记录不含前导0的数
  const notZeroLead = [];

  for (let num of nums) {
    if (num[0] == "0") {
      zeroLead.push(num);
    } else {
      notZeroLead.push(num);
    }
  }

  // 要使最终的组合数最小，则含前导0的数必须要组合在一起，且按照 a + b > b + a的规则排序
  if (zeroLead.length != 0) {
    zeroLead.sort((a, b) => (a + b > b + a ? 1 : a + b == b + a ? 0 : -1));
  }

  const combineZeroLead = zeroLead.join("");

  // 如果输入的数都是含前导0的，则直接返回combineZeroLead，需要去除左侧0，但是注意不能返回空串
  if (notZeroLead.length == 0) {
    const tmp = combineZeroLead.replace(/^0+/g, "");
    return tmp.length == 0 ? "0" : tmp;
  }

  // 将不含前导0的所有数进行字典序排序，将首位字典序最小的数都提取到heads中，他们都是head的可选值
  notZeroLead.sort();

  const heads = [notZeroLead.shift()];
  while (notZeroLead.length > 0 && heads[0][0] == notZeroLead[0][0]) {
    heads.push(notZeroLead.shift());
  }

  let ans;
  for (let i = 0; i < heads.length; i++) {
    // 选取某个head
    const head = heads[i];

    // 则heads剩下的数以及notZeroLead剩下的数将组成tail，依旧按照 a + b > b + a的规则排序，这样tail才能最小
    const tail = [...notZeroLead, ...heads.slice(0, i), ...heads.slice(i + 1)];
    tail.sort((a, b) => (a + b > b + a ? 1 : a + b == b + a ? 0 : -1));

    // 最终只记录整体最小数
    if (ans) {
      const tmp = head + combineZeroLead + tail.join("");
      if (tmp < ans) {
        ans = tmp;
      }
    } else {
      ans = head + combineZeroLead + tail.join("");
    }
  }

  return ans;
}

Python算法源码

import functools

# 输入获取
nums = input().split()


# 算法入口
def getResult(nums):
    # zeroLead列表记录含前导0的数
    zeroLead = []
    # notZeroLead列表记录不含前导0的数
    notZeroLead = []

    for num in nums:
        if num[0] == '0':
            zeroLead.append(num)
        else:
            notZeroLead.append(num)

    # 要使最终的组合数最小，则含前导0的数必须要组合在一起，且按照 a + b > b + a的规则排序
    if len(zeroLead) != 0:
        zeroLead.sort(key=functools.cmp_to_key(lambda a, b: 1 if a + b > b + a else 0 if a + b == b + a else -1))

    combineZeroLead = "".join(zeroLead)

    # 如果输入的数都是含前导0的，则直接返回combineZeroLead，需要去除左侧0，但是注意不能返回空串
    if len(notZeroLead) == 0:
        tmp = combineZeroLead.lstrip("0")
        return "0" if len(tmp) == 0 else tmp

    # 将不含前导0的所有数进行字典序排序，将首位字典序最小的数都提取到heads中，他们都是head的可选值
    notZeroLead.sort()

    heads = [notZeroLead.pop(0)]

    while len(notZeroLead) > 0 and heads[0][0] == notZeroLead[0][0]:
        heads.append(notZeroLead.pop(0))

    ans = None
    for i in range(len(heads)):
        # 选取某个head
        head = heads[i]

        # 则heads剩下的数以及notZeroLead剩下的数将组成tail，依旧按照 a + b > b + a的规则排序，这样tail才能最小
        tail = []
        tail.extend(notZeroLead)
        tail.extend(heads[:i])
        tail.extend(heads[i + 1:])

        tail.sort(key=functools.cmp_to_key(lambda a, b: 1 if a + b > b + a else 0 if a + b == b + a else -1))

        # 最终只记录整体最小数
        if ans is None:
            ans = head + combineZeroLead + "".join(tail)
        else:
            tmp = head + combineZeroLead + "".join(tail)
            if tmp < ans:
                ans = tmp

    return ans


# 算法调用
print(getResult(nums))