LeetCode_排序_中等_179.最大数
2023-09-27 14:25:46 时间
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————简单交换排序
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(因为 nums 中的值均为非负整数),直接返回 0 即可
if (nums[0] == 0) {
return "0";
}
res += Integer.toString(nums[i]);
}
return res;
}
相关文章
- Leetcode: Number Complement
- Leetcode: Product of Array Except Self
- LeetCode高频题:二叉树的锯齿形(Z字形,之字形)层序遍历
- LeetCode高频题14:最长公共前缀
- JS leetcode 寻找旋转排序数组中的最小值 题解分析,你不得不了解的二分法
- [LeetCode]剑指 Offer 47. 礼物的最大价值
- LeetCode之347前 K 个高频元素(相关话题:堆排序,桶排序)
- 【leetcode 桶排序】Maximum Gap
- 【leetcode】148:排序链表
- LeetCode 26. 删除排序数组中的重复项
- [LeetCode] 1122. Relative Sort Array 数组的相对排序
- [LeetCode] 937. Reorder Data in Log Files 日志文件的重新排序
- [LeetCode] Max Chunks To Make Sorted 可排序的最大块数
- [LeetCode] Sort Transformed Array 变换数组排序
- [LeetCode] Wiggle Sort II 摆动排序之二
- [LeetCode] 75. Sort Colors 颜色排序
- leetcode 637. Average of Levels in Binary Tree 二叉树的层平均值(简单)
- leetcode 769. Max Chunks To Make Sorted 最多能完成排序的块(中等)
- leetcode 153. Find Minimum in Rotated Sorted Array 寻找旋转排序数组中的最小值(中)
- leetcode 451. Sort Characters By Frequency 根据字符出现频率排序