【剑指offer第16天】排序

短命女 2022-09-12 12:58 143阅读 0赞

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAJ-alkw_size_20_color_FFFFFF_t_70_g_se_x_16]  
x+y > y+x 那么x>y x大于y那么x应排在y的右边，这里要重写快速排序算法。

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,nums.length-1);
            StringBuilder res = new StringBuilder();
            for(int i = 0;i < nums.length;i++){ 
                res.append(strs[i]);
            }
            return res.toString();
        }
        void quicksort(String[] strs,int l,int r){ 
            if(l >= r){ return;}
            int i = l;
            int j = r;
            String pivot = strs[i];
            while(i < j){ 
                while((strs[j] + strs[l]).compareTo(strs[l] + strs[j]) >= 0 && i < j) j--;
                while((strs[i] + strs[l]).compareTo(strs[l] + strs[i]) <= 0 && i < j) i++;
                String tmp = strs[i];
                strs[i] = strs[j];
                strs[j] = tmp;
            }
            strs[l] = strs[i];
            strs[i] = pivot;
            quicksort(strs, l, i - 1);
            quicksort(strs, i + 1, r);
        }
    }

快排，要注意最后的将low值更新和找到pivot变量的正确位置i，二分查找先执行j–

public static void quickSort(int[] arr, int low, int high) { 
                if (low > high)     return;
                int i = low;
                int j = high;
                int pivot = arr[low];
                
                while (i < j) { 
                    while(arr[j] >= pivot && i < j)     -- j;
                    while(arr[i] <= pivot && i < j)     ++ i;
                    if (i < j) { 
                        int t = arr[i];
                        arr[i] = arr[j];
                        arr[j] = t;
                    }
                }
                arr[low] = arr[i];
                arr[i] = pivot;
                quickSort(arr, low, j - 1);
                quickSort(arr, j + 1, high);
        }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAJ-alkw_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
只要最大值-最小值<5且没有重复数字就可以（大小王的0可以重复）

class Solution { 
        public boolean isStraight(int[] nums) { 
            int l = nums.length;
            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])return false;
            }
            return (nums[4] - nums[joker]) < 5;
        }
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAJ-alkw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/d52867f663d14a28904528ff323befc9.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAJ-alkw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/d4577a83345349e39cb1a1d04e7e521c.png