剑指Offer-把数组排成最小的数

描述:

输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。
例如:输入数组 {3,32,321},则打印出这三个数字能排成的最小数字为 321323。

分析:

这里需要找到排列中数值最小的字符串,那么应该将原数组进行排序处理,将数组中的每个数字看成字符串,在比较两个字符串 S1 和 S2 的大小时, 应该比较的是 S1+S2 和 S2+S1 的大小,如果 S1+S2 < S2+S1,那么应该把 S1 排在前面,否则应该把 S2 排在前面。两两比较,交换位置即可。
例如:

  • 第一步:{3,32,321}
  • 第二步:332>323,则将3和32两两交换位置,则得到{32,3,321}
  • 第三步:32321>32132,则将32和321两两交换位置,则得到{321,3,32}
  • 第四步:数组中的第一个位置已经确定了,接下来进行第二个位置,同理得到{321,32,3},此时循环结束,得到了我们要的数组。

最后,将数组拼接成字符串即可得到结果。

代码实现:

public  String PrintMinNumber(int[] numbers){
        int n = numbers.length;
      //循环数组,按照规则对数组进行排序处理
        for (int i=0;i<n;i++){
            for (int j=i+1;j<n;j++){
                String s12 = String.valueOf(numbers[i]) + String.valueOf(numbers[j]);
                String s21 = String.valueOf(numbers[j]) + String.valueOf(numbers[i]);
                if (Integer.parseInt(s12)>Integer.parseInt(s21)){
                    int t=numbers[i];
                    numbers[i]=numbers[j];
                    numbers[j]=t;
                }
            }

        }
      //使用StringBuilder拼接字符串,提高效率
        StringBuilder sb = new StringBuilder();
        for (int i:numbers){
            System.out.println(i);
            sb.append(i);
        }
        return sb.toString();

    }

题目链接

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 在C语言中,五种基本数据类型存储空间长度的排列顺序是: A)char B)char=int<=float C)ch...
    夏天再来阅读 3,435评论 0 2
  • 算法思想贪心思想双指针排序快速选择堆排序桶排序荷兰国旗问题二分查找搜索BFSDFSBacktracking分治动态...
    第六象限阅读 3,396评论 0 0
  • 前言 2. 实现 Singleton 3. 数组中重复的数字 4. 二维数组中的查找 5. 替换空格 6. 从尾到...
    Observer_____阅读 3,022评论 0 1
  • 第5章 引用类型(返回首页) 本章内容 使用对象 创建并操作数组 理解基本的JavaScript类型 使用基本类型...
    大学一百阅读 3,279评论 0 4
  • 永吉三十五中视野文学社精选100篇作品目录 1、诚信是不过时的美丽(姜畅) 2、诚信为人之本(王晴) 3、诚开金石...
    简思莼阅读 777评论 0 0