题目地址(45. 把数组排成最小的数)

https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/

题目描述

  1. 输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
  5. 示例 1:
  7. 输入: [10,2]
  8. 输出: "102"
  10. 示例 2:
  12. 输入: [3,30,34,5,9]
  13. 输出: "3033459"
  17. 提示:
  19. 0 < nums.length <= 100
  21. 说明:
  23. 输出结果可能非常大，所以你需要返回一个字符串而不是整数
  24. 拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0

前置知识


公司

  • 暂无

思路

主要就是一个点 比较 i+j 和j+i的大小 这个+是字符串拼接 , 将较小的排在前面, 也就是完成了排序 只不过不是按照数字的大小进行排序 而是按照比较拼接后字符串的大小作为条件来排序
我这里使用的是冒泡排序的方法来做的 可以使用快速排序来做 效率高一点

关键点


代码

  • 语言支持：Java

Java Code:

  1. class Solution {
  2.     public String minNumber(int[] nums) {
  3.         String[] strings = new String[nums.length];
  4.         for (int i = 0; i < nums.length; i++) {
  5.             strings[i] = String.valueOf(nums[i]);
  6.         }
  7.         for (int i = 0; i < strings.length; i++) {
  8.             for (int j = i; j < strings.length; j++) {
  9.                 if (((strings[i] + strings[j]).compareTo(strings[j] + strings[i])) > 0) {
  10.                     String temp = strings[i];
  11.                     strings[i] = strings[j];
  12.                     strings[j] = temp;
  13.                 }
  14.             }
  15.         }
  16.         StringBuilder stringBuilder = new StringBuilder();
  17.         for (int i = 0; i < strings.length; i++) {
  18.             stringBuilder.append(strings[i]);
  19.         }
  20.         return stringBuilder.toString();
  21.     }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：剑指 Offer 45. 把数组排成最小的数 - 图1#card=math&code=O%28n%29&id=JG0Vj)
  • 空间复杂度：剑指 Offer 45. 把数组排成最小的数 - 图2#card=math&code=O%28n%29&id=vhiYn)