数据结构与算法--将数组排成最小的数

迈不过友情╰ 2022-10-05 09:58 10阅读 0赞

#### 将数组排成最小的数 ####

*  题目：输入一个正整数的数组，将数组中所有数字拼接在一起排列成一个新的数，打印能拼接出来的所有数字中最小的一个，
 *  案例：输入数组\{12,4，55\}，则能打印出最小的数组是：12455
 *  首先还是最简单的做法，我们求出数组中所有数字的全排列，然后将每个排列的情况拼接成一个新的数字，比较得到最小的数字情况。求数组的全排列问题我们在之前的文章：[数据结构与算法–字符串的排列组合问题][Link 1]
 *  更具排列组合知识，n个数组共有n！个排列，当数组元素比较多的时候，时间复杂度会是一个非常大的数值，运行会非常慢，应该有更快的方案。
 *  常规优化：穷举法是为了避开了一个选择交换的过程，如果只有两个元素，我们找出小的放到前面，那这个题目就转成了一个找数组的排序规则的过程。数组根据这个排序规则排列成一个最小的数字。要确定排序规则，就需要比较两个数字，也就是给出 m，n两个数，我们需要确定一个排序规则判断m，n那个应该在前面，这不是比较数字大小的问题。
 *  根据题目要求，两个数字m，n，能拼出mn，nm两个数字。
    
     *  如果mn < nm，那么我们应该输出mn，也就是m应该在n前面，我们定义m 小于 n
     *  如果mn > nm，那么我们应该输出nm，也就是n在m前，我们定义n 小于 m
     *  同样mn = nm定义 m= n
     *  以上中 > < = 是我们数学意义上的比较，而大于，小于，等于，是我们自己定义的大小关系。
 *  那么我们接下来需要考虑的是怎么去拼接数字，当给出数字，m，n，我们直接计算的方式得到mn，nm的关系并不难。但是还有一个关键问题，当mn拼接后得到数字无法用int表达的时候，超过int类型的范围那么我们就不能用普通的计算方式。有一个潜在的大数问题让我必须用字符串的方式来计算。
 *  大数问题用字符串解决，字符串的比较问题，因为此处mn， nm 两个数必然是两个长度相等的字符串，那么比较他大小只需要按照字符串的大小比较规则就可以了。
 *  基于以上分析，我们可以先对数组中的所有数组进行快速排序
 *  排序规则用我们自定义规则，
 *  从小到大排序后，将所有数字依次拼接，就得到了最小值。
 *  经如上分析有如下代码：

/** * 将数组中所有数据合并成一个数，求出能排成的最小数 * * @author liaojiamin * @Date:Created in 12:00 2021/6/8 */
    public class FinMinNumber { 
    
        public static String pringMinNumber(int[] array) { 
            if (array == null || array.length <= 0) { 
                return "";
            }
            if (array.length == 1) { 
                return String.valueOf(array[0]);
            }
            String[] str = new String[array.length];
            for (int i = 0; i < array.length; i++) { 
                str[i] = String.valueOf(array[i]);
            }
            quickSort(str, 0, str.length - 1);
            StringBuilder stringBuilder = new StringBuilder();
            for (String s : str) { 
                System.out.print(s +", ");
                stringBuilder.append(s);
            }
            System.out.println();
            return stringBuilder.toString();
        }
    
        /** * 快排法，按从小到大排序字符串，字符串大小规则自定义 * */
        public static String[] quickSort(String[] str, Integer left, Integer right) { 
            if (left < right) { 
                Integer temp = quickSortSwap(str, left, right);
                quickSort(str, left, temp - 1);
                quickSort(str, temp + 1, right);
            }
            return str;
        }
    
        public static Integer quickSortSwap(String str[], Integer left, Integer right) { 
            if (left < right) { 
                String position = str[left];
                while (left < right){ 
                    while (left < right && myCompareTO(str[right], position) > 0) { 
                        right--;
                    }
                    if (left < right) { 
                        str[left] = str[right];
                        left++;
                    }
                    while (left < right && myCompareTO(str[left], position) < 0) { 
                        left++;
                    }
                    if (left < right) { 
                        str[right] = str[left];
                        right--;
                    }
                }
               str[left] = position;
            }
            return left;
        }
    
        /** * 字符串大小规则比较， * ab > ba => a>b * ab == ba => a==b * ab<ba => a<b * */
        public static Integer myCompareTO(String a, String b){ 
            String ab = a+b;
            String ba = b+a;
            return ab.compareTo(ba);
        }
    
        public static void main(String[] args) { 
            int[] str_1 = { 12, 34, 1, 34, 777, 33, 99, 86, 56, 9};
            System.out.println(pringMinNumber(str_1));
        }
    }

#### 后续问题 ####

*  如上实现方案中有两个问题：
    
     *  第一我定义了一种新的比较两个数的规则，但是这种规则是我们想出来的，并不是定理或者公
     *  第二我们定义的是比较两个数的规则，但是用它来排序一个包含多个数字的数组，最终得到的是否是我们需要的的最小数字？
 *  那么以上两点我们必须给出严格的数学证明，来确保方案的准确：
 *  第一，证明之前订阅的比较规则有效性。一个比较规则有效，需满足三个条件，自反性，对称性，传递性
    
     *  自反性： 显然，如果ab = ba， 那么 a等于b
     *  对称性： 如果a 小于 b，则ab < ba， 所以ba > ab,因此b 大于 a
     *  传递性： 如果a 小于 b， 则 ab < ba。 假设a， b都是十进制表示时候，分别有1位，m位，有如下推断  
        如果有a 小于b  
        ab = a \* 10 m \+ b  
        ba = b\* 101 \+ a  
        若 ab < ba  
        有 a \* 10 m \+ b < b\* 101 \+ a  
        a \* 10 m \- a < b\* 101 \- b  
        a(10m\-1) < b(101\-1)  
        a/(101\-1) < b/(10m\-1)  
        同时如果有b 小于c，则bc < cb，同样假设c十进制n位，与以上证明一致，得到  
        b/(10m \-1) < c(10n \-1)  
        综上： a/(101\-1) < b/(10m\-1) < c(10n \-1)  
        a/(101\-1) < c(10n \-1)  
        a(10n \-1) < c(101\-1)  
        a \* 10n \+ c < c \* 101\+a  
        ac < ca  
        a<c
 *  如上证明了这种比较规则满足自反性，对称性，传递性，是一种有效的比较规则，
 *  以下还需要证明根据如上规则将数组排序后，将数组中所有数字拼接起来得到的确实是最小值。
 *  略（太难了）

[上一篇：数据结构与算法-- 数组中出现次数超过一半的数字（时间复杂度的讨论）][--]  
[下一篇：数据结构与算法–丑数][Link 2]

[Link 1]: https://blog.csdn.net/liaojiamin0102/article/details/117223345
[--]: https://blog.csdn.net/liaojiamin0102/article/details/117356494
[Link 2]: https://blog.csdn.net/liaojiamin0102/article/details/117743362