「剑指Offer」Day16：排序（简单）

剑指 Offer 45. 把数组排成最小的数

题目描述

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

输入: [3,30,34,5,9] 输出: "3033459"

说明：

输出结果可能非常大，所以你需要返回一个字符串而不是整数
拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0

题目链接：https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/

思路

该题本质上是一个排序问题，设数组 numsnumsnums 中任意两数字的字符串为 xxx 和 yyy ，则规定排序判断规则如下：

若拼接字符串x+y > y+x ，则 x “大于” y ；
反之，若 x+y < y+x ，则 x “小于” y；

参考题解：链接：https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/solution/mian-shi-ti-45-ba-shu-zu-pai-cheng-zui-xiao-de-s-4/

方法一：快速排序

根据上面的排序判断规则，应用快速排序进行实现

class Solution {
    public String minNumber(int[] nums) {
        int length = nums.length;
        String[] strs = new String[length];
        for(int i = 0; i < length; i++){ //将整数转换为字符串存入一个字符串数组
            strs[i] = String.valueOf(nums[i]);
        }
        quickSort(strs, 0, length - 1);
        StringBuilder sbr = new StringBuilder();
        for(String str : strs){ //遍历拼接
            sbr.append(str);
        }
        return sbr.toString();
    }
    public void quickSort(String[] strs, int start, int end){ //快速排序
        if(start >= end){
            return;
        }
        int left = start;
        int right = end;
        String pivot = strs[start]; //确定基准元素
        while(left != right){
            //拼接基准元素，比较并交换
            while(left < right && (strs[right] + pivot).compareTo(pivot + strs[right]) >= 0){
                right--;
            }
            while(left < right && (strs[left] + pivot).compareTo(pivot + strs[left]) <= 0){
                left++;
            }
            if(left < right){
                String temp = strs[left];
                strs[left] = strs[right];
                strs[right] = temp;
            }
        }
        strs[start] = strs[left];
        strs[left] = pivot;
        int pivotIndex = left;
        quickSort(strs, start, pivotIndex - 1); //对左边继续进行分治
        quickSort(strs, pivotIndex + 1, end); //对右边继续进行分治
    }
}

方法二：调用内置函数

调用内置函数，根据排序判断规则进行排序， $Arrays.sort(strs, (x, y) -> (x + y).compareTo(y + x));$

class Solution {
    public String minNumber(int[] nums) {
        int length = nums.length;
        String[] strs = new String[length];
        for(int i = 0; i < length; i++){ //将整数转换为字符串存入一个字符串数组
            strs[i] = String.valueOf(nums[i]);
        }
        //调用内置函数，根据排序判断规则进行排序
        Arrays.sort(strs, (x, y) -> (x + y).compareTo(y + x));
        StringBuilder sbr = new StringBuilder();
        for(String str : strs){ //遍历拼接
            sbr.append(str);
        }
        return sbr.toString();
    }
}

剑指 Offer 61. 扑克牌中的顺子

题目描述

从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。

输入: [0,0,1,2,5] 输出: True
说明：大、小王为 0 ，可以看成任意数字，有两个0，2到5之间刚好缺少3，4，可使用0代替

链接：https://leetcode-cn.com/problems/bu-ke-pai-zhong-de-shun-zi-lcof

思路

根据题意为顺子的规则：

除大小王外，所有牌无重复；
设此 5 张牌中最大的牌为 max，最小的牌为 min （大小王除外），则需满足：max-min < 5

参考题解：https://leetcode-cn.com/problems/bu-ke-pai-zhong-de-shun-zi-lcof/solution/mian-shi-ti-61-bu-ke-pai-zhong-de-shun-zi-ji-he-se/

代码实现

class Solution {
    public boolean isStraight(int[] nums) {
        int joker = 0; //大小王的数量
        Arrays.sort(nums); //排序
        for(int i = 0; i < 4; i++){
            if(nums[i] == 0){ //为大小王就累加数量
                joker++;
                continue;
            }
            if(nums[i] == nums[i+1]){ //有重复直接返回false
                return false;
            }
        }
        //此时joker标识的是最小值，要求最大值-最小值小于5，才为顺子
        return nums[4] - nums[joker] < 5;
    }
}