[数据结构与算法]【乱序版 ● 剑指offer】每日算法题打卡题解—— 排序（题号 404561）

打卡day12

第一题：剑指 Offer 45. 把数组排成最小的数

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

示例 1:
输入: [10,2]
输出: “102”

示例 2:
输入: [3,30,34,5,9]
输出: “3033459”

提示:
0 < nums.length <= 100

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof

解题思路：
求拼接起来的最小数字，本质是个排序问题。
利用快速排序，快速排序模板

void Quick_Sort(int *arr, int begin, int end){
    if(begin > end)
        return;
    int tmp = arr[begin];
    int i = begin;
    int j = end;
    while(i != j){
        while(arr[j] >= tmp && j > i)
            j--;
        while(arr[i] <= tmp && j > i)
            i++;
        if(j > i){
            int t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
        }
    }
    arr[begin] = arr[i];
    arr[i] = tmp;
    Quick_Sort(arr, begin, i-1);
    Quick_Sort(arr, i+1, end);
}

java代码：

class Solution {
    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]);
         }
        quickSort(strs, 0, strs.length - 1);
        StringBuilder res = new StringBuilder();//创建可变字符串
        for(String s : strs){
            res.append(s);//拼接字符串
        }
        return res.toString();
    }
    void quickSort(String[] strs, int left, int right) {//快速排序
        if(left >= right){
        	return;
        }
        int l = left, r = right;
        String tmp = strs[l];
        while(l < r) {
            while((strs[r] + strs[left]).compareTo(strs[left] + strs[r]) >= 0 && l < r) {//比较字符串大小
            	r--;
            }
            while((strs[l] + strs[left]).compareTo(strs[left] + strs[l]) <= 0 && l < r) {
            	l++;
            }
            //交换l和r的值
            tmp = strs[l];
            strs[l] = strs[r];
            strs[r] = tmp;
        }
        strs[l] = strs[left];
        strs[left] = tmp;
        quickSort(strs, left, l - 1);
        quickSort(strs, l + 1, right);
    }
}

第二题：剑指 Offer 61. 扑克牌中的顺子

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

示例 1:
输入: [1,2,3,4,5]
输出: True

示例 2:
输入: [0,0,1,2,5]
输出: True

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/bu-ke-pai-zhong-de-shun-zi-lcof

解题思路：
由题意，五张牌中，最大的牌 - 最小的牌 的值 小于5
可以对数组进行排序，遍历判断是否有重复。然后获取最大和最小的牌进行比较。
java代码：

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++; // 统计大小王数量
            }
            else if(nums[i] == nums[i + 1]) return false; // 若有重复，提前返回 false
        }
        return nums[4] - nums[joker] < 5; // 最大牌 - 最小牌 < 5 则可构成顺子
    }
}

第三题：剑指 Offer 40. 最小的k个数

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

示例 1：
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]

示例 2：
输入：arr = [0,1,2,1], k = 1
输出：[0]

限制：
0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof

解题思路：
利用快速排序

java代码：

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0 || arr.length == 0) {
            return new int[0];
        }
        // 最后一个参数表示我们要找的是下标为k-1的数
        return quickSearch(arr, 0, arr.length - 1, k - 1);
    }

    private int[] quickSearch(int[] nums, int lo, int hi, int k) {
        // 每快排切分1次，找到排序后下标为j的元素，如果j恰好等于k就返回j以及j左边所有的数；
        int j = partition(nums, lo, hi);
        if (j == k) {
            return Arrays.copyOf(nums, j + 1);
        }
        // 否则根据下标j与k的大小关系来决定继续切分左段还是右段。
        return j > k? quickSearch(nums, lo, j - 1, k): quickSearch(nums, j + 1, hi, k);
    }

    // 快排切分，返回下标j，使得比nums[j]小的数都在j的左边，比nums[j]大的数都在j的右边。
    private int partition(int[] nums, int lo, int hi) {
        int v = nums[lo];
        int i = lo, j = hi + 1;
        while (true) {
            while (++i <= hi && nums[i] < v);
            while (--j >= lo && nums[j] > v);
            if (i >= j) {
                break;
            }
            int t = nums[j];
            nums[j] = nums[i];
            nums[i] = t;
        }
        nums[lo] = nums[j];
        nums[j] = v;
        return j;
    }
}