力扣 - 剑指 Offer 45. 把数组排成最小的数
2021/10/24 6:09:52
本文主要是介绍力扣 - 剑指 Offer 45. 把数组排成最小的数,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目
剑指 Offer 45. 把数组排成最小的数
思路1
- 将整数数组转化成字符串数组
- 然后使用Arrays工具类的sort方法帮助我们排序
代码
class Solution { public String minNumber(int[] nums) { int length = nums.length; // 将整数数组转化成字符串数组 String[] str = new String[length]; for (int i = 0; i < length; i++) { str[i] = String.valueOf(nums[i]); } // 使用Java自带排序 Arrays.sort(str, new Comparator<String>() { @Override public int compare(String o1, String o2) { return (o1+o2).compareTo(o2+o1); } }); // 将字符串数组里的按顺序拼接 StringBuilder sb = new StringBuilder(); for (String s : str) { sb.append(s); } return sb.toString(); } }
复杂度分析
- 时间复杂度:\(O(NlogN)\)
- 空间复杂度:\(O(N)\)
思路2
- 自定义排序规则
- 可以使用冒泡排序比较好理解一点,也可以使用快速排序
- 排序规则是这样的,通过拼接字符串拼接xy:
- 如果
x+y > y+x
,那么说明x
大于y
- 如果
x+y < y+x
,那么说明x
小于y
- 如果
- 按照这个排序规则,可以得出类似升序排序,升序排序是前面的数字要小于后面的数字,这个题目也是要求前面的数字在该题环境下要小于后面的数字
- 因此我们可以得出以下代码:
代码
class Solution { public String minNumber(int[] nums) { int length = nums.length; // 将整数数组转化成字符串数组 String[] str = new String[length]; for (int i = 0; i < length; i++) { str[i] = String.valueOf(nums[i]); } // 自定义排序规则的快速排序 quickSort(str, 0, length-1); // 将字符串数组里的按顺序拼接 StringBuilder sb = new StringBuilder(); for (String s : str) { sb.append(s); } return sb.toString(); } public void quickSort(String[] arr, int left, int right) { String pivot = arr[(left + right) / 2]; int l = left; int r = right; while (l <= r) { // 因为left+pivot要满足大于pivot+left,然后和右边的交换,这样子小的才能在左边 while ((arr[l] + pivot).compareTo(pivot + arr[l]) < 0) { l++; } // 因为right+pivot要满足小于pivot+right,然后和左边的交换,这样子大的才能在右边 while ((arr[r] + pivot).compareTo(pivot + arr[r]) > 0) { r--; } // 这一步进行交换,就是将大的移到右边,小的移到左边 if (l <= r) { String temp = arr[l]; arr[l] = arr[r]; arr[r] = temp; l++; r--; } } // 递归左边 if (r > left) { quickSork(arr, left, r); } // 递归右边 if (l < right) { quickSork(arr, l, right); } } }
复杂度分析
- 时间复杂度:\(O(NlogN)\)
- 空间复杂度:\(O(N)\)
思路3
- 和思路2一样,也是使用快速排序,只是快速排序实现的方法不一样
代码
class Solution { public String minNumber(int[] nums) { int length = nums.length; // 将整数数组转化成字符串数组 String[] str = new String[length]; for (int i = 0; i < length; i++) { str[i] = String.valueOf(nums[i]); } // 快速排序 quickSork(str, 0, length-1); // 将字符串数组里的按顺序拼接 StringBuilder sb = new StringBuilder(); for (String s : str) { sb.append(s); } return sb.toString(); } public void quickSork(String[] arr, int left, int right) { if (left < right) { int l = left; int r = right; String pivot = arr[l]; while (l < r) { // 因为升序,所以right要大于pivot while (l < r && (arr[r] + pivot).compareTo(pivot + arr[r]) >= 0) { r--; } arr[l] = arr[r]; // 因为升序,所以left要小于于pivot while (l < r && (arr[l] + pivot).compareTo(pivot + arr[l]) <= 0) { l++; } arr[r] = arr[l]; } arr[l] = pivot; quickSork(arr, left, l-1); quickSork(arr, l+1, right); } } }
复杂度分析
- 时间复杂度:\(O(NlogN)\)
- 空间复杂度:\(O(N)\)
这篇关于力扣 - 剑指 Offer 45. 把数组排成最小的数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-20登录鉴权入门:打造安全的用户认证系统
- 2024-09-20动态表格入门:新手必读教程
- 2024-09-20动态菜单项入门:轻松掌握基础知识
- 2024-09-20动态面包屑入门:轻松掌握面包屑导航技巧
- 2024-09-20动态权限入门:新手必读指南
- 2024-09-20动态主题处理入门:轻松掌握网站主题切换技巧
- 2024-09-20富文本编辑器入门:新手必读指南
- 2024-09-20功能权限入门:轻松掌握权限管理基础
- 2024-09-20后台管理系统开发入门:新手必读教程
- 2024-09-20后台开发入门:新手必读教程