天天看点

LeetCode_排序_中等_179.最大数1.题目2.思路3.代码实现(Java)

目录

  • 1.题目
  • 2.思路
  • 3.代码实现(Java)

1.题目

给定一组非负整数 nums,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数。

注意:输出结果可能非常大,所以你需要返回一个字符串而不是整数。

示例 1:

输入:nums = [10,2]

输出:“210”

示例 2:

输入:nums = [3,30,34,5,9]

输出:“9534330”

示例 3:

输入:nums = [1]

输出:“1”

示例 4:

输入:nums = [10]

输出:“10”

提示:

1 <= nums.length <= 100

0 <= nums[i] <= 109

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/largest-number

2.思路

(1)利用简单交换排序的思想对数组元素进行排序,不过排序的规则所有变化,先将要排序的两个数nums[i]和nums[j]转换为字符串a和b,然后用函数compareTo()比较a+b与b+a的大小,a+b==b+a返回0,a+b>b+a返回正数,a+b<b+a返回负数。由于简单交换排序的特点,即每完成一趟排序,就至少会有一个元素的位置确定,所以可以在排序的同时对结果进行字符串的拼接。

3.代码实现(Java)

//(1)思路1
public String largestNumber(int[] nums) {
    int length=nums.length;
    if(length==1){
        return Integer.toString(nums[0]);
    }
    int tmp;
    String res="";
    for(int i=0;i<length;i++){
        for(int j=i+1;j<length;j++){
            String a=Integer.toString(nums[i]);
            String b=Integer.toString(nums[j]);
            if((a+b).compareTo(b+a)<0){
                tmp=nums[i];
                nums[i]=nums[j];
                nums[j]=tmp;
            }
        }
        //如果排序后的第一个元素是0,那其后面的元素肯定≤0,直接返回0即可
        if(nums[0]==0) return "0";
        res+=Integer.toString(nums[i]);
    }
    return res;
}