每天一道劍指offer-把數組排成最小的數

• 2019 年 10 月 4 日
• 筆記

前言

今天的題目 每天的題目見github(看最新的日期): https://github.com/gzc426 具體的題目可以去牛客網對應專題去找。

題目

每天一道劍指offer-把數組排成最小的數 來源： https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7?tpId=13&tqId=11180&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

題目詳述

輸入一個正整數數組，把數組裡所有數字拼接起來排成一個數，打印能拼接出的所有數字中最小的一個。例如輸入數組{3，32，321}，則打印出這三個數字能排成的最小數字為321323。

思路

和昨天的那道題一樣，全排列數組中所有的情況，把所有結果存到treeSet裏面，然後由於是treeSet是按照從小到大排序的，所有返回第一個結果就行。

題目詳解

import java.util.*;  public class Solution {      public String PrintMinNumber(int [] numbers) {          if(numbers.length == 0)              return "";          TreeSet<String> set = new TreeSet<>();          PrintMinNumber(numbers,0,set);          return set.pollFirst();      }      public void PrintMinNumber(int [] numbers,int index,TreeSet<String> set)      {          if(index == numbers.length-1)          {              String tempStr = "";              for(int i=0;i<numbers.length;i++)                  tempStr += String.valueOf(numbers[i]);              set.add(tempStr);          }else{              for(int i=index;i<numbers.length;i++)              {                  swap(numbers,index,i);                  PrintMinNumber(numbers,index+1,set);                  swap(numbers,index,i);              }          }      }      public void swap(int [] numbers,int i,int j)      {          int temp = numbers[i];          numbers[i] = numbers[j];          numbers[j] = temp;      }  }