给定一个长度为n的数组nums，数组由一些非负整数组成，现需要将他们进行排列并拼接，每个数不可拆分，使得最后的结果最大，返回值需要是string类型，否则可能会溢出。
数据范围：
，
进阶：时间复杂度)
，空间复杂度：)
[编程题]最大数
public String solve (int[] nums) {
// write code here
StringBuilder res=new StringBuilder();
PriorityQueue<Integer> queue=new PriorityQueue<Integer>(new Comparator<Integer>(){
@Override
public int compare(Integer num1 ,Integer num2){
return (num2+""+num1).compareTo(num1+""+num2);
}
});
for(int num:nums){
queue.add(num);
}
while(!queue.isEmpty()){
res.append(queue.poll());
}
return res.charAt(0)=='0'?"0":res.toString();
}
编辑于 2024-03-09 16:46:33
回复(0)
变相的排序问题，只是修改了排序的判定方法
import java.util.*;
public class Solution {
class AAAA {
int val;
String num;
int length = 0;
boolean isUesd = false;
public AAAA(int val) {
this.val = val;
this.num = String.valueOf(val);
this.length = this.num.length();
}
}
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 最大数
* @param nums int整型一维数组
* @return string字符串
*/
public String solve (int[] nums) {
// write code here
StringBuilder sb = new StringBuilder();
AAAA[] res = new AAAA[nums.length];
for (int i = 0; i < nums.length; i++) {
res[i] = new AAAA(nums[i]);
}
while (true) {
int index = -1;
for (int i = 0; i < res.length; i++) {
if (res[i].isUesd) {
continue;
}
index = i;
}
if (index < 0) break;
for (int j = 0; j < res.length; j++) {
if (!res[j].isUesd && compare(res[index], res[j]) < 0) {
index = j;
}
}
res[index].isUesd = true;
if (sb.length() == 0 && res[index].val == 0) {
continue;
}
sb.append(res[index].num);
}
if (sb.length() > 0) {
return sb.toString();
} else {
return "0";
}
}
public long compare(AAAA a1, AAAA a2) {
long n1 = 1, n2 = 1;
for (int i = 0; i < a2.length; i++) {
n1 = n1 * 10;
}
n1 = n1 * a1.val + a2.val;
for (int i = 0; i < a1.length; i++) {
n2 = n2 * 10;
}
n2 = n2 * a2.val + a1.val;
return n1 - n2;
}
}
发表于 2023-08-19 19:42:21
回复(0)
import java.util.*;
public class Solution {
/**
* 最大数
* @param nums int整型一维数组
* @return string字符串
*/
public String solve (int[] nums) {
// write code here
//冒泡排序，降序排列，小的数往后冒
for(int i = 0; i < nums.length; i++){
for(int j = 0; j < nums.length - i - 1; j++){
//数值排序时，考虑十位数与个位数的拼接
//保存拼接的字符串，拼接字符串
String a = String.valueOf(nums[j]);
String b = String.valueOf(nums[j+1]);
String sum1 = a+b,sum2 = b+a;
//转换成基本数据类型才能比较
int temp1 = Integer.parseInt(sum1),temp2=Integer.parseInt(sum2);
//若temp1>temp2，则说明a（nums[j]）在拼接时放在前面，nums[j]与nums[j+1]不用交换
//若temp1<temp2，则说明b（nums[j+1]）在拼接时放在前面，发生交换
if(temp1<temp2){
int temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
}
}
}
String str = new String();
for(int i = 0; i < nums.length; i++){
str += nums[i];
}
if(str.length()!=0 && str.charAt(0) == '0'){
return "0";
}else{
return str;
}
}
}
发表于 2022-08-16 11:29:09
回复(0)
import java.util.*;
public class Solution {
/**
* 最大数
* @param nums int整型一维数组
* @return string字符串
*/
public String solve (int[] nums) {
PriorityQueue<String> queue = new PriorityQueue<String>(new Comparator<String>(){
@Override
public int compare(String s1,String s2){
if(s2.charAt(0)==s1.charAt(0)){
return Integer.parseInt(s2+s1)-Integer.parseInt(s1+s2);
}
return s2.charAt(0)-s1.charAt(0);
}
});
for(int i=0;i<nums.length;++i){
queue.offer(String.valueOf(nums[i]));
}
StringBuilder sb = new StringBuilder();
while(!queue.isEmpty()){
sb.append(queue.poll());
}
while(sb.length()>1){
if(sb.charAt(0)=='0'){
sb.deleteCharAt(0);
}
else
break;
}
return sb.toString();
}
}
发表于 2022-07-25 16:15:19
回复(0)
本题关键就是自定义比较规则，然后选取一个排序方法就可以了，就冒泡冒的熟练于是就直接冒泡了，冒泡好处是可以一边冒泡一边拼串；
public class Solution {
/**
* 最大数
* @param nums int整型一维数组
* @return string字符串
*/
public int compare(int num1, int num2) {
return ("" + num1 + num2).compareTo("" + num2 + num1);
}
public String solve (int[] nums) {
// write code here
int len = nums.length;
StringBuilder builder = new StringBuilder("");
for (int i = 0; i < len; ++i) {
for (int j = len - 1; j > i ; --j) {
if (compare(nums[j], nums[j - 1]) > 0) {
int tmp = nums[j];
nums[j] = nums[j - 1];
nums[j - 1] = tmp;
}
}
if (nums[0] == 0) { // 特例特判
return "0";
}
builder.append(nums[i]);
}
return builder.toString();
}
}
发表于 2022-07-04 08:40:43
回复(1)
import java.util.*;
public class Solution {
/**
* 最大数
* @param nums int整型一维数组
* @return string字符串
*/
public String solve (int[] nums) {
// write code here
ArrayList<String> list = new ArrayList<>();
StringBuilder sb = new StringBuilder();
for(int i = 0; i < nums.length; i++){
list.add(String.valueOf(nums[i]));
}
Collections.sort(list,new Comparator<String>(){
public int compare(String a, String b){
return (b+a).compareTo(a+b);
}
});
if(list.get(0).equals("0")){
return "0";
}
for(String str : list){
sb.append(str);
}
return sb.toString();
}
}
发表于 2021-12-20 08:44:58
回复(0)
public class Solution {
public String solve (int[] nums) {
String[] str = new String[nums.length];
for (int i = 0; i < nums.length; i++)
str[i] = nums[i] + "";
for (int i = 0; i < nums.length; i++){
for (int j = 0; j < nums.length - 1; j++){
if ((str[j] + str[j + 1]).compareTo(str[j + 1] + str[j]) > 0){
String temp = str[j];
str[j] = str[j + 1];
str[j + 1] = temp;
}
}
}
if(str[nums.length - 1].equals("0")) return "0";
StringBuffer res = new StringBuffer();
for (int i = nums.length - 1; i >= 0; i--)
res.append(str[i]);
return res.toString();
}
} 我是***
发表于 2021-11-20 17:03:58
回复(0)
public class Solution {
public String solve (int[] nums) {
int n = nums.length;
String[] strs = new String[n];
for(int i = 0; i < n; i++){
strs[i] = String.valueOf(nums[i]);
}
Arrays.sort(strs, new Comparator<String>(){
public int compare(String a, String b){
return (b + a).compareTo(a + b);
}
});
if(strs[0].equals("0"))
return "0";
StringBuilder ans = new StringBuilder();
for(int i = 0; i < n; i++){
ans.append(strs[i]);
}
return ans.toString();
}
}
发表于 2021-10-19 13:20:52
回复(0)
public class Solution {
/**
* 最大数
* @param nums int整型一维数组
* @return string字符串
*/
public String solve (int[] nums) {
String result = "";
for (int i = 1; i < nums.length; i++) {
int n=i;
while (n>0){
if (bijiao(nums[n],nums[n-1])==1) {
int temp = nums[n];
nums[n] = nums[n-1];
nums[n-1]=temp;
n--;
}else{
break;
}
}
}
for (int i=0;i< nums.length;i++) {
if(nums[0]==0) return 0+"";
result+=nums[i];
}
return result;
}
public static int bijiao(int a, int b){
char[] A = (a+"").toCharArray();
char[] B = (b+"").toCharArray();
int len = A.length>B.length?B.length:A.length;
int nv1 = 0,nv2=0;
if (A.length<B.length) {
nv1=-2;nv2=2;
char[] tep = A;
A=B;
B=tep;
}
for (int i = 0; i < len; i++) {
if(A[i]>B[i]){
return 1+nv1;
}else if(A[i]==B[i] && i==len-1){
if (A.length==B.length || A[i+1]>B[0]) {
return 1+nv1;
}else{
return -1+nv2;
}
}else if(A[i]<B[i]){
return -1+nv2;
}
}
return 0;
}
}
发表于 2021-10-17 17:44:01
回复(0)
import java.util.*;
public class Solution {
/**
* 最大数
* @param nums int整型一维数组
* @return string字符串
*/
public String solve (int[] nums) {
// write code here
String[] strs = new String[nums.length];
for (int i = 0; i < nums.length; i++) {
strs[i] = "" + nums[i];
}
for (int i = 0; i < strs.length - 1; i++) {
for (int j = strs.length -1; j >= i + 1; j--) {
if (compare(strs[j],strs[j - 1]) > 0) {
String temp = strs[j];
strs[j] = strs[j - 1];
strs[j - 1] = temp;
}
}
}
String ans = "";
for (int i = 0; i < strs.length; i++) {
ans = ans + strs[i];
}
Set<Character> set = new HashSet<Character>();
for (int i = 0; i < ans.length(); i++) {
set.add(ans.charAt(i));
}
if (set.contains('0') && set.size() == 1) {
return "0";
}
return ans;
}
Integer compare(String s1, String s2) {
char[] chars1 = s1.toCharArray();
char[] chars2 = s2.toCharArray();
int min = Math.min(chars1.length, chars2.length);
for (int i = 0; i < min; i++) {
if (chars1[i] > chars2[i]) {
return 1;
} else if (chars1[i] < chars2[i]) {
return -1;
}
}
int f = min;
if (chars1.length > chars2.length) {
char c = chars2[min - 1];
for (int j = f; j < chars1.length; j++) {
if (chars1[j] > c) {
return 1;
} else if (chars1[j] < c){
return -1;
}
}
}
if (chars1.length < chars2.length) {
char c = chars1[min - 1];
for (int j = f; j < chars2.length; j++) {
if (chars2[j] > c) {
return -1;
} else if (chars2[j] < c){
return 1;
}
}
}
return 0;
}
}
发表于 2021-09-17 18:54:22
回复(0)
import java.util.*;
public class Solution {
/**
* 最大数
* @param nums int整型一维数组
* @return string字符串
*/
public String solve (int[] nums) {
// write code here
if (nums == null || nums.length == 0) {
return "";
}
List<String> res = new ArrayList<>();
for (int val : nums) {
res.add(String.valueOf(val));
}
Collections.sort(res, (a, b) -> (b + a).compareTo(a + b));
StringBuilder sb = new StringBuilder();
if (res.get(0).equals("0")) return "0";
for (String s : res) {
sb.append(s);
}
return sb.toString();
}
}
发表于 2021-09-01 17:40:59
回复(0)
public class Solution {
/**
* 最大数
* @param nums int整型一维数组
* @return string字符串
*/
public String solve (int[] nums) {
// write code here
String[] arr = new String[nums.length];
for(int i = 0; i < nums.length; i++){
arr[i] = String.valueOf(nums[i]);
}
Arrays.sort(arr,(a,b)->{
return (a+b).compareTo(b+a);
});
String res = "";
for(int i = arr.length-1; i >= 0; i--){
res += arr[i];
}
if(res.charAt(0) == '0')
return "0";
return res;
}
}
/**
* 最大数
* @param nums int整型一维数组
* @return string字符串
*/
public String solve (int[] nums) {
// write code here
String[] arr = new String[nums.length];
for(int i = 0; i < nums.length; i++){
arr[i] = String.valueOf(nums[i]);
}
Arrays.sort(arr,(a,b)->{
return (a+b).compareTo(b+a);
});
String res = "";
for(int i = arr.length-1; i >= 0; i--){
res += arr[i];
}
if(res.charAt(0) == '0')
return "0";
return res;
}
}
发表于 2021-08-22 21:33:00
回复(0)
public String solve (int[] nums) {
List<String> list = new ArrayList<>();
for(int num : nums)list.add(String.valueOf(num));
list.sort((a,b) -> (a + b).compareTo(b + a));
StringBuilder sb = new StringBuilder();
for (int i=list.size()-1;i>=0;i--) sb.append(list.get(i));
if(sb.charAt(0)=='0') return "0";
return sb.toString();
}
编辑于 2021-07-15 21:30:36
回复(0)
重写Comparator接口的compare方法。官方API介绍：
比较它的两个参数的顺序。当第一个参数小于、等于或大于第二个参数时，返回一个负整数、零或正整数。
在前面的描述中，符号sgn(表达式)表示数学符号函数，它定义根据表达式的值是负、零还是正返回-1、0或1中的一个。
实现者必须确保所有x和y的sgn(compare(x, y)) == -sgn(compare(y, x))。(这意味着当且仅当compare(y, x)抛出异常时，compare(x, y)必须抛出异常。)
实现者还必须确保关系是可传递的:((compare(x, y)>0) && (compare(y, z)>0))意味着比较(x, z)>0。
最后，实现者必须确保对于所有的z, compare(x, y)==0意味着sgn(compare(x, z))==sgn(compare(y, z))。
通常情况下，但并不严格要求(compare(x, y)==0) == (x = (y))。一般来说，任何违反这一条件的比较国都应明确指出这一事实。推荐的语言是“注意:这个比较器强加的顺序与等号不一致。”
参数:
O1 -第一个被比较的对象。
O2——第二个要比较的物体。
返回:
作为第一个参数的负整数、零或正整数小于、等于或大于第二个参数。
public class Solution {
/**
* 最大数
* @param nums int整型一维数组
* @return string字符串
*/
public String solve (int[] nums) {
// write code here
String[] ss = new String[nums.length];
StringBuilder sb = new StringBuilder();
for(int i = 0; i < nums.length; i++) {
ss[i] = String.valueOf(nums[i]);
}
Arrays.sort(ss, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return Integer.valueOf(o2 + o1) - Integer.valueOf(o1 + o2);
}
});
if(ss[0].equals("0")) return "0";
for(int i = 0; i < ss.length; i++) {
sb.append(ss[i]);
}
return sb.toString();
}
}
发表于 2021-06-17 10:40:24
回复(0)
使用最大堆来记录大小关系
public class Solution {
/**
* 最大数
* @param nums int整型一维数组
* @return string字符串
*/
public String solve (int[] nums) {
// write code here
if(nums == null || nums.length == 0) return "";
PriorityQueue<String> pq = new PriorityQueue<String>(this::compare);
for(int num : nums){
pq.offer(num+"");
}
StringBuilder sb = new StringBuilder();
while (! pq.isEmpty()){
sb.append(pq.poll());
}
if(sb.charAt(0) == '0') return "0";
return sb.toString();
}
int compare(String a, String b){
int aSize = a.length(), bSize = b.length();
int size = Math.min(aSize, bSize);
for(int i = 0; i < size; i ++){
if(a.charAt(i) == b.charAt(i)) continue;
return b.charAt(i) - a.charAt(i);
}
if(aSize == bSize) return 0;
return compare(a+b, b+a);
}
}
编辑于 2021-05-12 10:27:51
回复(0)
emm，算是内存占用比较小的解法吧！
/**
* 思路；一定要写比较器，比如 30 和 20101，一定是 30 放在前面，
* 对于 9 92 一定是 9 放在前面！
* 对于排序的逻辑可以用插入即可
*/
public String solve(int[] nums) {
// write code here
for (int i = 1; i < nums.length; i++) {
if (compare(nums[i], nums[i - 1])) {
int temp = nums[i];
int j = i - 1;
while (j >= 0 && compare(temp, nums[j])) {
nums[j+1] = nums[j--];
}
nums[j + 1] = temp;
}
}
StringBuilder stringBuilder = new StringBuilder("" + nums[0]);
for (int i = 1; i < nums.length; i++) {
stringBuilder.append("" + nums[i]);
}
String res = stringBuilder.toString();
while (res.startsWith("0") && res.length() > 1) {
res = res.substring(1);
}
return res;
}
/**
* 比较两个数，如 30 20102 ，从首位依次比较，直到数据短的一方比完为止；
* 如 9 92 一定是 9 在前，本比较器是精华呀！好多小伙伴使用 Arrays,sort();比大小是不是有些浪费呢？
* @param num1
* @param num2
* @return 数据大的返回 true；num1 放在前面
*/
public boolean compare(int num1, int num2) {
String str1 = String.valueOf(num1);
String str2 = String.valueOf(num2);
for (int i = 0; i < Math.min(str1.length(), str2.length()); i++) {
if (str1.charAt(i) < str2.charAt(i)) return false;
}
return true;
}
发表于 2021-03-28 10:48:13
回复(0)
问题信息
通过挑战的用户
查看代码-
2023-02-02 09:38:52
-
2022-09-28 21:35:04 -
2022-09-18 23:54:43
-
2022-09-16 01:07:27
-
2022-09-15 16:09:05
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
