最小组合数

• 前言
• 一、新的排序规则
• • 1、库函数
  • 2、希尔排序
• 总结

前言

对于排序来说，我们是针对目标来排序，如本题针对的是组合的数是否是最小，所以排序的时候就根据两两之间的组合来看谁小。这都是针对要解决问题本身所产出不一样的排序规则。

一、新的排序规则

可以使用自定义的排序，可以用库函数。

1、库函数

import java.util.Arrays;

public class MinNumber45 {
    public String minNumber(int[] nums) {
        //转化为字符串更方便比较
        String[] strs = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            strs[i] = String.valueOf(nums[i]);
        }
        //库函数排序
        Arrays.sort(strs,((o1, o2) -> (o1+o2).compareTo(o2+o1)));
        //将排好的数组通过库函数连接起来。join的底层也是stringbuilder.
        return String.join("",strs);
    }
}

2、希尔排序

//希尔排序
    public String minNumber2(int[] nums) {
        //比较最高位数
        String[] strs = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            strs[i] = String.valueOf(nums[i]);
        }
        for (int d = nums.length / 2; d > 0; d = d / 2) {
            for (int i = d; i < nums.length; i++) {
                if ((strs[i] + strs[i - d]).compareTo(strs[i - d] + strs[i]) < 0) {
                    String temp = strs[i];
                    int j = i - d;
                    for (; j >= 0 && (strs[j] + temp).compareTo(temp + strs[j]) > 0; j = j - d) {
                        strs[j + d] = strs[j];
                    }
                    strs[j + d] = temp;
                }
            }
        }
        return String.join("", strs);
    }

总结

排序要根据目标是什么来排序。一般的是简单的升序和降序。