[剑指offer]面试题第[45]题[JAVA][把数组排成最小的数][快排][ Comparator][PriorityQueue]

Bertha 。 2023-02-28 12:56 20阅读 0赞

#### 【问题描述】\[中等\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]

#### 【解答思路】 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]

###### 1. 快速排序 ######

![在这里插入图片描述][20200721163237978.png]

**时间复杂度：O(N^2) 空间复杂度：O(1)**

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

###### 2. 内置函数 ######

![在这里插入图片描述][20200721163228360.png]

**时间复杂度：O(N) 空间复杂度：O(1)**

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();
        }
    }

###### 3. PriorityQueue ######

**时间复杂度：O(NlogN) 空间复杂度：O(N)**

class Solution { 
        /** * 各种组合方式位数都是一样的， => 谁高位小，就选谁; * 因此本质上就是根据这个做排序，难点在于如何判断优先级 * 判断高位优先级有好几种办法, * 1.拿出两个数字，逐位对比 vs 位数不相同时，处理比较麻烦 * 2.两个数字加和,例如 n , m 对应有 n * pow(10,m) + m 和 m * pow(10,n) + n，谁小选谁，但是int溢出 * 3.直接字符串相加， "nm" 与 "mn" 作比较。 * tips： * 1.影响性能的关键就在于排序算法了; * 2.经过思考，两个数字的优先级与其他数字无关！ * */
        public static int compare (int num1 , int num2) { 
            if (num1 == num2) return 0;
            String nm = new String(num1 + "" + num2);
            String mn = new String(num2 + "" + num1);
            return nm.compareTo(mn);
        }
    
        public static String minNumber(int[] nums) { 
            if (nums == null || nums.length == 0) return "";
            String rx = "";
            int n = nums.length;
            PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((o1, o2) -> compare(o1,o2));
            for (int num : nums) { 
                priorityQueue.add(num);
            }
            while (!priorityQueue.isEmpty()) { 
                rx += priorityQueue.poll();
            }
            return rx;
        }
    }

#### 【总结】 ####

###### 1.快排最后不熟悉 ######

void fastSort(String[] strs, int l, int r) { 
            if(l >= r) return;
            int i = l, j = r;
            String tmp = 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++;
                tmp = strs[i];
                strs[i] = strs[j];
                strs[j] = tmp;
                //当i==j时 tmp=ij交汇处的值 
            }
            //最后把“ij交互处”置换成基准值
            strs[i] = strs[l];
            
            strs[l] = tmp;
            fastSort(strs, l, i - 1);
            fastSort(strs, i + 1, r);
        }

**等价于**

void fastSort(String[] strs,int l ,int r){ 
            if(l>=r) return ;
            int i = l,j =r;
            String key= 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;
            }
            //先把”ij交互处置的值“挪到前排
            strs[l] = strs[i];
            
            //最后把“ij交互处”置换成基准值
            strs[i] = key;
    
            fastSort(strs, l, i - 1);
            fastSort(strs, i + 1, r);
        }

###### 2. Arrays.sort(strs, (x, y) -> (x + y).compareTo(y + x)); ######

转载链接：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/

Java实现快排：https://blog.csdn.net/qq\_36186690/article/details/82470451

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: /images/20230209/842e822ad7db419fb2c2ae2323fb0d8b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200721163142877.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/2020072116315346.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[20200721163237978.png]: https://img-blog.csdnimg.cn/20200721163237978.png
[20200721163228360.png]: https://img-blog.csdnimg.cn/20200721163228360.png