【Java每日编程题】牛客网编程题:数串排序

本文主要是介绍【Java每日编程题】牛客网编程题:数串排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

设有n个正整数，将他们连接成一排，组成一个最大的多位整数。
如:n=3时，3个整数13,312,343,连成的最大整数为34331213。
如:n=4时,4个整数7,13,4,246连接成的最大整数为7424613。
输入描述

有多组测试样例，每组测试样例包含两行，第一行为一个整数N（N<=100），第二行包含N个数(每个数不超过1000，空格分开)。

输出描述:

每组数据输出一个表示最大的整数。

示例1

输入
2 12 123 4 7 13 4 246
输出
12312 7424613

过程

开始理解错了题目,来来回回的尝试了好几遍才弄清楚题目的大致意思,试了很多遍才过.,一开始就很轻敌,后来才发现没有想的那么容易
这里写图片描述

解题思路

第一次输入的int型作为元素的数量
后面输入作为元素的值
这里的承载题我选择了LinkedList和String[]
拿到数组或链表后进行排序
这里的排序并不是比较值的大小
排序结果要求最后的组合值最大!
所以一开始就应该思考”什么才是组合值最大”
例如:[9,987,4,65]这四个元素的组合值9987654是最大组合值
我用的排序方法是冒泡排序
排序思路是,直接比较两个相邻元素的组合值,因为两个元素只有两种组合值,把小值排后
最后拿到的就是最组合值
PS:之前试过’按位比较’+’数值比较’的思路,[85,9,96]的最大组合就是99685,首位最大的放在前面,首位最小的放在后面,但是这样有很多bug,索性直接拿相邻两位元素的拼接值进行比较,不会出错

解答代码

LinkedList版

import java.util.*;
import java.lang.*;public class Main{public static void main(String[] args) {Collection<Integer> list = new LinkedList<>();Scanner input = new Scanner(System.in);int number = 0; int tempinput = 0;String endstring = "";while(true){tempinput = input.nextInt();if(tempinput!=0&&tempinput<=100){number = tempinput;break;}}for(int i=0;i<number;i++){int element = input.nextInt();if(element!=0&&element<=1000){list.add(element);}}for(int j=list.size()-1;j>0;j--){for(int k=0;k<j;k++){String preelement = Integer.toString(((LinkedList<Integer>) list).get(k)).substring(0,1);String Nextelement = Integer.toString(((LinkedList<Integer>) list).get(k+1)).substring(0,1);if(Integer.parseInt(preelement)<Integer.parseInt(Nextelement)){int templow = ((LinkedList<Integer>) list).get(k);int tempbig = ((LinkedList<Integer>) list).get(k+1);((LinkedList<Integer>) list).set(k,tempbig);((LinkedList<Integer>) list).set(k+1,templow);}}}for(int l=0;l<list.size();l++){endstring = endstring+((LinkedList<Integer>) list).get(l);}System.out.println(endstring);}}

字符串数组版

import java.util.*;
import java.lang.*;public class Main {public static void main(String[] args) {Scanner input = new Scanner(System.in);int number = 0; int tempinput = 0;String endstring = "";while(true){tempinput = input.nextInt();if(tempinput!=0&&tempinput<=100){number = tempinput;break;}}String[] list = new String[number];for(int i=0;i<number;i++){int element = input.nextInt();if(element!=0&&element<=1000){list[i] = Integer.toString(element);}}for(int j=list.length-1;j>0;j--){for(int k=0;k<j;k++){String preelement = list[k] +""+list[k+1];String Nextelement = list[k+1] +""+ list[k];if(Integer.parseInt(preelement)<Integer.parseInt(Nextelement)){String templow = list[k];String tempbig = list[k+1];list[k] = tempbig;list[k+1] = templow;}}}for(int l=0;l<list.length;l++){endstring = endstring + list[l];}System.out.println(endstring);}}