把数组排成最小的数

---

题目：

题解：

解题思路：

• 若拼接字符串 x + y > y + x ，则 x “大于” y ；

• 反之，若 x + y < y + x ，则 x “小于” y ；

• 

复杂度分析：

• 时间复杂度 O(NlogN) ： N 为最终返回值的字符数量（ strs 列表的长度 ≤N ）；使用快排或内置函数的平均时间复杂度为 O(NlogN) ，最差为 O(N^2)。
• 空间复杂度 O(N) ： 字符串列表 strs 占用线性大小的额外空间。

1、快速排序

• 代码：

  class Solution {
      public String minNumber(int[] nums) {
          // 1、将int数组转变为字符串数组
          String[] strs = new String[nums.length];
          for (int i = 0; i < nums.length; i++) {
              strs[i] = String.valueOf(nums[i]);
          }
  
          // 2、使用快速排序将strs进行此题的规律排序（从“小”到“大”）
          quickSort(strs,0,strs.length - 1);
  
          // 3、将排完序的数组以字符串的方式返回
          StringBuilder res = new StringBuilder();
          for (String s : strs) {
              res.append(s);
          }
          return res.toString();
      }
  
      // 快速排序
      private void quickSort(String[] strs, int l, int r) {
          if (l >= r) return;
  
          int i = l, j = r;
  
          while(i < j) {
              /*
              * 若拼接字符串 x + y > y + x ，则 x “大于” y ；
                反之，若 x + y < y + x ，则 x “小于” y ；
              * */
              // 判断当strs[j]“大于等于”strs[l]，j--
              while (i < j && (strs[j] + strs[l]).compareTo(strs[l] + strs[j]) >= 0) j--;
              // 判断当strs[i]“小于等于”strs[l]，i++
              while (i < j && (strs[i] + strs[l]).compareTo(strs[l] + strs[i]) <= 0) i++;
  
              // 如果i = j，交换i 和 l
              if (i == j) {
                  String tmp = strs[i];
                  strs[i] = strs[l];
                  strs[l] = tmp;
              }else { // 否则交换i 和 j，交换后，strs[j]就大于strs[l]，strs[i]就小于strs[l]
                  String tmp = strs[i];
                  strs[i] = strs[j];
                  strs[j] = tmp;
              }
          }
  
          quickSort(strs,l,i-1);
          quickSort(strs,i+1,r);
      }
  }

• 优化后代码：

  // 快速排序优化，将i = j放到了外面，减少了每次循环的判断
  class Solution2 {
      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 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;
          quickSort(strs, l, i - 1);
          quickSort(strs, i + 1, r);
      }
  }

2、内置函数

• 代码：

  // 内置函数
  class Solution3 {
      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();
      }
  }