前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >给定一个字符串数组,按照字典顺序进行从小到大的排序

给定一个字符串数组,按照字典顺序进行从小到大的排序

作者头像
mathor
发布2018-08-17 15:41:36
1.2K0
发布2018-08-17 15:41:36
举报
文章被收录于专栏:mathormathor

 假设字符串数组是str[] = {"ab","cd","ef"},很明显答案就是”abcdef“最小,其实这是一道贪心问题,我的想法是将字符串数组进行内的字符串数组进行排序,这个大思路是没错的,但问题是怎么排序,str[i] < str[j]?这样其实不行,举个反例str[] = {"b","ba"},如果按照那个贪心策略排序,得到的答案是"bba",但实际上“bab”更小,后来仔细以想,贪心策略应该是str[i] + str[j] < str[j] + str[i],有兴趣的大家可以下去证明,还是比较好证的

代码语言:javascript
复制
import java.util.*;

public class Main {
    public static class MyCompara implements Comparator<String> {
        public int compare(String s1, String s2) {
            String tmp1 = s1 + s2;
            String tmp2 = s2 + s1;
            return tmp1.compareTo(s2);
        }
    }
    public static String minString(String[] str) {
        String res = "";
        Arrays.sort(str,new MyCompara());
        for(int i = 0;i < str.length;i++)
            res += str[i];
        return res;
    }
    public static void main(String[] args) {
        System.out.println(minString(new String[] {"ab","ef","cd"}));
    }
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018-08-09,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档