首页 > 试题广场 >

数组排成最小的数

[编程题]数组排成最小的数

热度指数：1420 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

输入一个正整数数组，将它们连接起来排成一个数，输出能排出的所有数字中最小的一个。

输入描述:

一行输入，数组中的数字用逗号隔开。例如：

输入为：

32,231

则表示数组{32, 231}

输出描述:

直接输出最小数字即可，如示例题目中，输出为：

23132

示例1

输入

32,231

输出

算法知识视频讲解

morooi

import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] strings = sc.nextLine().split(",");
        Arrays.sort(strings, (s1, s2) -> (s1 + s2).compareTo((s2 + s1)));
        for (String s : strings) {
            System.out.print(s);
        }
    }
}

发表于 2020-08-13 14:00:40 回复(0)

有点小菜哦

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        String[] strs = s.split(",");
        Arrays.sort(strs, new Comparator<String>() {
				public int compare(String a, String b){
                     for (int i = 0; i < a.length() || i < b.length(); i++) {
                        char aa = i < a.length() ? a.charAt(i):a.charAt(0);
                        char bb = i < b.length() ? b.charAt(i):b.charAt(0);
                        if (aa > bb) {
                            return 1;
                        } else if (aa < bb) {
                            return -1;
                        }
                    }
                    return 0;
				}
			});
        StringBuilder res = new StringBuilder();
        for (String s1 : strs) {
            res.append(s1);
        }
        System.out.println(res);
    }
}

发表于 2020-06-08 20:54:04 回复(1)

牛客279810500号

直接输出就AC了

#include<bits/stdc++.h>
using namespace std;

static bool cmp(int &a, int &b)
{
	string s1 = to_string(a) + to_string(b);
	string s2 = to_string(b) + to_string(a);
	return s1<s2;
}
int main()
{
	vector<int>a;
	int num;
	cin >> num;
	a.push_back(num);
	while (cin.get() != '\n')
	{
		cin >> num;
		a.push_back(num);
	}
	
	long long ans = 0;
	string res;
	if (a.size() == 0)ans=0;
	sort(a.begin(), a.end(), cmp);
	for (int i = 0; i<a.size(); i++)
	{
		res += to_string(a[i]);
	}
	cout <<res<< endl;
	return 0;

}

编辑于 2020-08-13 16:11:49 回复(3)

无辄_

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
 
// 括号处理 + 自定义比较器
/**
 * 输入一个正整数数组，将它们连接起来排成一个数，输出能排出的所有数字中最小的一个。
 * 输入描述:
 * 一行输入，数组中的数字用逗号隔开。例如：
 * 输入为：
 * 32,231
 * {32, 231}
 *
 * 输出描述:
 * 直接输出最小数字即可，如示例题目中，输出为：
 * 23132
 * */
 
//如何处理逗号?
//如何处理最小数据: 设置排序顺序 将最小的数放在最前位置即可
 
public class Main {
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        //开始拆分s
        String[] strings = s.split(",");
        //将strings进行转换为int[]
        int[] arrVals = new int[strings.length];
 
        for(int i = 0;i < strings.length;i++){
            arrVals[i] = Integer.parseInt(strings[i]);
        }
 
        //转换成功 可以写核心算法
        getMinVal(arrVals);
    }
 
    public static void getMinVal(int[] vals){
        String[] strings = new String[vals.length];
        for(int i = 0;i < vals.length;i++){
            strings[i] = String.valueOf(vals[i]);
        }
 
        //开始进行自定义的比较器选择
        Arrays.sort(strings, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return (o1 + o2).compareTo(o2 + o1);
            }
        });
        //比较结束后 直接进行反馈值
        String res = "";
        for(String str : strings){
            res += str;
        }
        System.out.println(res);
    }
}

发表于 2020-07-27 15:10:51 回复(0)

竹秋

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = null;
        str = in.nextLine();
        String[] split = str.split(",");
        ArrayList<String> list = new ArrayList<>();
        for (String s : split) {
            list.add(s);
        }
 
        ArrayList<String> sortList = sortList(list);
        String result = "";
        for (String s : sortList) {
            result += s;
        }
        System.out.println(result);
    }
 
 
    public static ArrayList<String> sortList(ArrayList<String> strings) {
        if (strings == null) {
            return null;
        }
        Collections.sort(strings, (o1, o2) -> {
            if (o1 == null || o2 == null) {
                return 0;
            }
            int len = o1.length() <= o2.length() ? o1.length() : o2.length();
            for (int i = 0; i < len; i++) {
                String t1 = o1.substring(i, i+1);
                String t2 = o2.substring(i, i+1);
                if (o1.charAt(i) == o2.charAt(i)) {
                    continue;
                } else if (o1.charAt(i) > o2.charAt(i)) {
                    return 1;
                } else if (o1.charAt(i) < o2.charAt(i)) {
                    return -1;
                }
            }
            return -1;  //  如果较长的那个字符串前几位和较短的一样，那么判定较长的字符串更小
        });
         
//        strings.sort(String::compareTo);   // 使用这个compareTo时，会认定较短的那个字符串更小
        return strings;
    }
}

发表于 2020-03-16 21:12:08 回复(0)

是不困呀

之前代码有误，参考楼下@morooi写法😂😂😂

import java.util.*;

public class Test {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String input = sc.next();
        String[] arr = input.split(",");
        Arrays.sort(arr, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return (o1 + o2).compareTo(o2 + o1);
            }
        });
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
        }
    }
}

编辑于 2020-08-14 08:39:04 回复(10)

王登锋

#include <bits/stdc++.h>
using namespace std;

string _min = "";
vector<string> res;
vector<bool> used;

void compare(string& a, string& min){
    int len = a.size();
    if(min.empty()){
        min = a;
        return;
    }

    for(int i =0; i<len; ++i){
        int _1 = a[i]-'0';
        int _2 = min[i] - '0';
        if(_1 < _2){
            min = a;
            return;
        } else if(_1 > _2) return; //这一步不能忘!
    }
}// min = min

void dfs(vector<string>& arr){
    int len = arr.size();
    if(res.size() == len){
        string temp = "";
        for(string v : res){
            temp += v;
        }
        compare(temp,_min);//操作了全局变量_min了!
        return;
    }


    for(int i =0; i<len; ++i){
        if(used[i]) continue;

        res.emplace_back(arr[i]);
        used[i] = true;
        dfs(arr);
        res.pop_back();
        used[i] = false;
    }
}

int main(){
    vector<string>data;
    int num;
    cin >> num;
    data.push_back(to_string(num));
    while (cin.get() != '\n')
    {
        cin >> num;
        data.push_back(to_string(num));
    }

        if(data.empty()) return 0;
    used.resize(data.size(),false);

    //dfs bt
    dfs(data);
    cout << _min << endl;
    return 0;
}

回溯dfs搞定

编辑于 2022-10-05 13:46:37 回复(0)

重新开始也很美好

import java.util.*;
public class Main{
    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        String[] numbers = in.nextLine().split(",");
        Arrays.sort(numbers, new Comparator<String>() {
            @Override
            public int compare(String str1, String str2) {
                return (str1+str2).compareTo(str2+str1);
            }
        });
        String res = "";
        for(int i = 0; i < numbers.length; i++) {
            res += numbers[i];
        }
        System.out.println(res);
    }
}

发表于 2020-09-04 15:42:15 回复(0)

孤天祭

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        String[] sr=sc.nextLine().split(",");
        Arrays.sort(sr,(o1,o2)->(o1+o2).compareTo(o2+o1));
        for(int i=0;i<sr.length;i++){
            System.out.print(sr[i]);
        }
    }
}

对String的常用方法还是不熟

发表于 2020-09-03 22:28:24 回复(0)

露西恩缇努维尔

#include<bits/stdc++.h>
using namespace std;

bool cmp(string &s1,string &s2)
{
    int i=0,j=0;
    while(i<s1.size() && j<s2.size())
    {
        if(s1[i]>s2[j])
            return false;
        else if(s1[i]<s2[j])
            return true;
        else
            i++,j++;
    }
    if(i<s1.size() && s1[i]<s2[0])    return true;
    if(i<s1.size() && s1[i]>=s2[0])    return false;
    
    if(j<s2.size() && s2[j]>=s1[0])    return true;
    if(j<s2.size() && s2[j]>=s1[0])    return false;
    return true;
}

int main()
{
    string s;
    while(getline(cin,s))
    {
        vector<string> v;
        int st=0;
        while(st<s.size())
        {
            int pos=s.find(',',st);
            if(pos==string::npos)
            {
                v.push_back(s.substr(st,s.size()-st));
                break;
            }
            else
            {
                v.push_back(s.substr(st,pos-st));
                st=pos+1;
            }
        }
        sort(v.begin(),v.end(),cmp);
        string ans;
        for(auto &str:v)
            ans+=str;
        cout<<ans<<endl;   
    }
    return 0;
}

发表于 2020-09-03 16:47:41 回复(0)

Java

村花铁柱

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
String s = scanner.nextLine();
String[] strings = s.split(",");
Arrays.sort(strings, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return (o1 + o2).compareTo(o2 + o1);
}
});
String res = "";
for(String str : strings){
res += str;
}
System.out.println(res);
}
}

发表于 2020-08-13 23:02:00 回复(0)

天帆

import java.util.*;

public class Main {
    static Scanner sc =new Scanner(System.in);

    public static void main(String[] args) {
        String str =sc.nextLine();
        String[] strArr =str.split(",");
        for (int i=0;i<strArr.length-1;i++){
            int min_index=i;
            String  temp;
            for (int j=i+1;j<strArr.length;j++){
                String str_a=strArr[min_index];
                String str_b=strArr[j];
                if ((str_b+str_a).compareTo(str_a+str_b)<0){
                    min_index=j;
                }
            }
            temp=strArr[min_index];
            strArr[min_index]=strArr[i];
            strArr[i]=temp;
        }
        String outStr="";
        for (int i=0;i<strArr.length;i++){
            outStr+=strArr[i];
        }
        System.out.println(outStr);
    }
}

编辑于 2020-08-10 23:03:25 回复(0)

xlwmfh

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        String[] str = s.split(",");
        List<String> list = new ArrayList<>(Arrays.asList(str));
        list.sort((o1, o2) -> {
            for (int i = 0; i < o1.length() || i < o2.length(); i++) {
                char c1 = i >= o1.length() ? o1.charAt(i - 1) : o1.charAt(i);
                char c2 = i >= o2.length() ? o2.charAt(i - 1) : o2.charAt(i);
                if (c1 > c2) {
                    return 1;
                } else if (c1 < c2) {
                    return -1;
                }
            }
            return 0;
        });
        StringBuilder result = new StringBuilder();
        for (String s1 : list) {
            result.append(s1);
        }
        System.out.println(result);
    }
}

发表于 2020-04-10 16:37:44 回复(1)