算法的学习笔记—把数组排成最小的数(牛客JZ45)

举报
尘觉 发表于 2024/08/30 21:25:40 2024/08/30
【摘要】 在编程面试中,经常会遇到需要将问题转化为排序问题的题目。这些问题看似复杂,但只要抓住核心思路,便能迅速解决。今天我们就来看一道这样的题目:如何将一个非负整数数组拼接成最小的数字。

😀前言
在编程面试中,经常会遇到需要将问题转化为排序问题的题目。这些问题看似复杂,但只要抓住核心思路,便能迅速解决。今天我们就来看一道这样的题目:如何将一个非负整数数组拼接成最小的数字

🥰把数组排成最小的数

题目链接

牛客网

🤔题目描述

给定一个非负整数数组 numbers,要求将数组里的所有数字拼接起来,形成一个新的数字,并返回其中最小的那个。例如:

  • 输入数组 [3, 32, 321],我们可以将这些数字拼接成 321323,这个数字是所有可能拼接结果中的最小值。
  1. 输出结果可能非常大,所以你需要返回一个字符串而不是整数

  2. 拼接起来的数字可能会有前导 0,最后结果不需要去掉前导 0

数据范围:

0<=len(numbers)<=100

示例输入输出

  • 输入:[11, 3]
    • 返回值:"113"
  • 输入:[]
    • 返回值:""(空字符串)
  • 输入:[3, 32, 321]
    • 返回值:"321323"

🥰解题思路

解决这个问题的关键在于如何定义两个数字在拼接时的优先级。直观地,我们需要比较两个数字 S1S2 在不同顺序下拼接的结果。

例如,对于两个数字 332

  • 如果 S1 = "3"S2 = "32",那么 S1+S2"332"S2+S1"323"。显然,"323" 更小,因此我们应该将 32 排在 3 前面。

通过这种比较方式,我们可以定义一个自定义的排序规则,接着使用 Java 中的 Arrays.sort 方法进行排序,最终得到最小的拼接结果。

💖实现代码

以下是用 Java 实现的代码:

import java.util.Arrays;

public class MinNumber {

    public String PrintMinNumber(int[] numbers) {
        // 判断输入是否为空或长度为0,如果是则返回空字符串
        if (numbers == null || numbers.length == 0)
            return "";

        int n = numbers.length;
        // 创建一个字符串数组,用于存储每个数字的字符串形式
        String[] nums = new String[n];
        for (int i = 0; i < n; i++) {
            // 将数字转换为字符串并存储到字符串数组中
            nums[i] = String.valueOf(numbers[i]);
        }

        // 使用自定义的排序规则对字符串数组进行排序
        // 排序规则:如果拼接结果 s1+s2 小于 s2+s1,则 s1 排在前面
        Arrays.sort(nums, (s1, s2) -> (s1 + s2).compareTo(s2 + s1));

        // 使用 StringBuilder 来拼接排序后的字符串数组
        StringBuilder ret = new StringBuilder();
        for (String str : nums) {
            ret.append(str);
        }

        // 返回拼接后的字符串结果
        // 注意:此处不需要去除可能存在的前导0,因为题目没有要求去除
        return ret.toString();
    }
}

代码详解

  1. 字符串数组初始化:首先,我们将整数数组 numbers 转换为字符串数组 nums,这是因为在后续操作中,我们需要比较字符串拼接的结果。
  2. 自定义排序规则:接着,我们利用 Arrays.sort 方法对字符串数组进行排序。排序时,比较的关键是拼接后的字符串 s1+s2s2+s1 的大小。如果 s1+s2 小于 s2+s1,那么 s1 应该排在 s2 前面。
  3. 拼接结果:排序完成后,将排序好的字符串数组拼接成一个字符串,并返回这个最终结果。

复杂度分析

  • 时间复杂度:排序算法的时间复杂度为 O(n log n),其中 n 是数组的长度。由于每次比较涉及字符串的拼接操作,因此整体的时间复杂度还会受到字符串长度的影响。
  • 空间复杂度:主要空间消耗在字符串数组 nums 上,空间复杂度为 O(n)

😄总结

通过这道题目,我们看到了如何将一个复杂的拼接问题转化为排序问题,并且掌握了一种自定义排序规则的方法。这种思想不仅仅适用于本题,很多涉及组合或排列的问题都可以通过类似的思路来解决。

这道题目在许多面试中都会出现,它不仅考察了候选人的编程能力,更测试了对排序算法的理解与应用能力。希望通过本文的讲解,你能够掌握这一重要的编程技巧,并在实际开发中灵活运用。

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。