把数组排成最小的数

题目描述

思路

本题是遇到的第一道自定义排序的题

这类题目关键是要理清排序规则，比如本题中"30"+"3"<"3"+"30"，所以"30"<"3"

字符串化+插入排序

将每个元素字符串化，然后拼接调用compareTo()方法结合排序规则，使用插入排序，最后再从头到尾拼接在一起即可

小规模排序一般插入是首选，但是本题建议快排，因为100也不算小了，其实希尔都会比插入更好，可能是因为代码量前者少且前者好理解

字符串化+快速排序

代码实现

字符串化+插入排序

class Solution {
    public String minNumber(int[] nums) {
        String [] numsStr=new String[nums.length];
        for(int i=0;i<nums.length;i++){
            numsStr[i]=nums[i]+"";
        }
        for(int i=1;i<numsStr.length;i++){
            String cur = numsStr[i];
            int j=i;
            for(j=i;j>=1;j--){
                String s1=cur+numsStr[j-1];
                String s2=numsStr[j-1]+cur;
                if(s1.compareTo(s2)<0){
                    numsStr[j]=numsStr[j-1];
                }else{
                    break;
                }

            }
            numsStr[j]=cur;

        }
        StringBuilder result = new StringBuilder();
        for(String s:numsStr){
            result.append(s);
        }
        return result.toString();
    }
}

字符串化+快速排序

public class Solution {
    public String minNumber(int[] nums) {
        String[] numsStr = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            numsStr[i] = nums[i] + "";
        }
        quickSort(numsStr, 0, numsStr.length - 1);
        StringBuilder result = new StringBuilder();
        for(String s:numsStr){
            result.append(s);
        }
        return result.toString();
    }
    public void quickSort(String[] numsStr,int l,int r){
        if(l>=r){
            return;
        }
        int i = l, j = r, d = l;
        String cur = null, target = null,tmp = numsStr[i];;
        while (i < j) {
            cur = numsStr[j] + numsStr[d];
            target = numsStr[d] + numsStr[j];
            while (i < j && cur.compareTo(target) >=0) {//找比基准点小的值
                j--;
                cur = numsStr[j] + numsStr[d];
                target = numsStr[d] + numsStr[j];
            }
            cur = numsStr[i] + numsStr[d];
            target = numsStr[d] + numsStr[i];
            while (i < j && cur.compareTo(target) <= 0) {//找比基准点大的值
                i++;
                cur = numsStr[i] + numsStr[d];
                target = numsStr[d] + numsStr[i];
            }
            tmp=numsStr[i];
            numsStr[i] = numsStr[j];
            numsStr[j] = tmp;
        }
        numsStr[i]=numsStr[d];
        numsStr[d]=tmp;
        quickSort(numsStr, l, i - 1);
        quickSort(numsStr, i + 1, r);
    }
}

排序代码简化

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]);
        Arrays.sort(strs, (x, y) -> (x + y).compareTo(y + x));
        StringBuilder res = new StringBuilder();
        for(String s : strs)
            res.append(s);
        return res.toString();
    }
}

复杂度分析

时间复杂度

插入排序O(N^{2)，快速排序平均O(NlogN)，最坏O(N}2)，注意Arrays.Sort()底层是快速排序

空间复杂度

均为O(N)

反思不足

思路

这种自定义排序的题排序规则是重点

快速排序不熟悉

java se

String类的compareTo()可以按字典序判断括号里的比调用者大还是小，大返回正数，小返回负数

Arrays.sort()可以给数组排序，并且可以传函数自定义规则，可以用lambda语法

扑克牌中的顺子

题目描述

思路

set集合去重+最值之差

本题能推出是顺子的充分条件为不含有除0之外的重复元素+最大最小值之差小于5

代码实现

class Solution {
    HashSet<Integer> set=new HashSet<Integer>();
    public boolean isStraight(int[] nums) {
        int max=0,min=14;
        for(int num:nums){
            if(num==0)continue;
            if(!set.add(num)){
                return false;
            }
            max=num>max?num:max;
            min=num<min?num:min;
        }
        return max-min<5;
    }
}

复杂度分析

时间复杂度

O(1)

空间复杂度

O(1)

反思不足

思路

他人想的充分条件往往很简单，而我的往往很复杂