把數(shù)組排成最小的數(shù)

題目描述

輸入一個正整數(shù)數(shù)組萄唇,把數(shù)組里所有數(shù)字拼接起來排成一個數(shù)巩检,打印能拼接出的所有數(shù)字中最小的一個。例如輸入數(shù)組{3焕刮,32舶沿,321}墙杯,則打印出這三個數(shù)字能排成的最小數(shù)字為321323配并。

分析

最直接的方法是,將這幾個數(shù)做全排列高镐,得到所有可能的組合溉旋,然后對組合排序,選出最小的數(shù)嫉髓。第二種方法是观腊,設(shè)計一種排序方法,字符串m和n拼接算行,如果mn >nm,那么字符串n應(yīng)該排在m的前面梧油。

代碼一

public String PrintMinNumber(int [] numbers) {
        if(numbers == null || numbers.length == 0) return "";
        String[] nums = new String[numbers.length];
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<numbers.length;i++)
            nums[i] = ""+numbers[i];
        Arrays.sort(nums,new Comparator<String> () {
            public int compare(String o1,String o2) {
                return (o1+o2).compareTo(o2+o1);
            }
        });
        for(int i=0;i<numbers.length;i++)
            sb.append(nums[i]);
        return sb.toString();
    }

代碼二:全排列

ArrayList<String> res = new ArrayList<>();

    public String PrintMinNumber(int [] numbers) {
        permutation(numbers,0);
        String[] nums = new String[res.size()];
        for(int i=0;i<res.size();i++)
            nums[i] = res.get(i);
        Arrays.sort(nums);
        return nums[0];
    }
    
    private void permutation(int[] numbers,int pos) {
        if(pos >= numbers.length) {  
            StringBuilder sb = new StringBuilder();
            for(int i=0;i<numbers.length;i++)
                sb.append(""+numbers[i]);
            res.add(sb.toString());
            return;
        }
        for(int i=pos;i<numbers.length;i++) {
            swap(numbers,pos,i);
            permutation(numbers,pos+1);
            swap(numbers,pos,i);
        }
    }

    private void swap(int[] numbers, int i,int j) {
        int tmp = numbers[i];
        numbers[i] = numbers[j];
        numbers[j] = tmp;
    }
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市州邢,隨后出現(xiàn)的幾起案子儡陨,更是在濱河造成了極大的恐慌,老刑警劉巖,帶你破解...
    沈念sama閱讀 216,372評論 6 498
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件骗村,死亡現(xiàn)場離奇詭異嫌褪,居然都是意外死亡,警方通過查閱死者的電腦和手機胚股,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,368評論 3 392
  • 文/潘曉璐 我一進店門笼痛,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人琅拌,你說我怎么就攤上這事缨伊。” “怎么了进宝?”我有些...
    開封第一講書人閱讀 162,415評論 0 353
  • 文/不壞的土叔 我叫張陵倘核,是天一觀的道長。 經(jīng)常有香客問我即彪,道長紧唱,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 58,157評論 1 292
  • 正文 為了忘掉前任隶校,我火速辦了婚禮漏益,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘深胳。我一直安慰自己绰疤,他們只是感情好,可當我...
    茶點故事閱讀 67,171評論 6 388
  • 文/花漫 我一把揭開白布舞终。 她就那樣靜靜地躺著轻庆,像睡著了一般。 火紅的嫁衣襯著肌膚如雪敛劝。 梳的紋絲不亂的頭發(fā)上余爆,一...
    開封第一講書人閱讀 51,125評論 1 297
  • 那天,我揣著相機與錄音夸盟,去河邊找鬼蛾方。 笑死,一個胖子當著我的面吹牛上陕,可吹牛的內(nèi)容都是我干的桩砰。 我是一名探鬼主播,決...
    沈念sama閱讀 40,028評論 3 417
  • 文/蒼蘭香墨 我猛地睜開眼释簿,長吁一口氣:“原來是場噩夢啊……” “哼亚隅!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起庶溶,我...
    開封第一講書人閱讀 38,887評論 0 274
  • 序言:老撾萬榮一對情侶失蹤煮纵,失蹤者是張志新(化名)和其女友劉穎沉删,沒想到半個月后,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體醉途,經(jīng)...
    沈念sama閱讀 45,310評論 1 310
  • 正文 獨居荒郊野嶺守林人離奇死亡矾瑰,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,533評論 2 332
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了隘擎。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片殴穴。...
    茶點故事閱讀 39,690評論 1 348
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖货葬,靈堂內(nèi)的尸體忽然破棺而出采幌,到底是詐尸還是另有隱情,我是刑警寧澤震桶,帶...
    沈念sama閱讀 35,411評論 5 343
  • 正文 年R本政府宣布休傍,位于F島的核電站,受9級特大地震影響蹲姐,放射性物質(zhì)發(fā)生泄漏磨取。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 41,004評論 3 325
  • 文/蒙蒙 一柴墩、第九天 我趴在偏房一處隱蔽的房頂上張望忙厌。 院中可真熱鬧,春花似錦江咳、人聲如沸逢净。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,659評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽爹土。三九已至,卻和暖如春踩身,著一層夾襖步出監(jiān)牢的瞬間胀茵,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 32,812評論 1 268
  • 我被黑心中介騙來泰國打工惰赋, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留宰掉,地道東北人。 一個月前我還...
    沈念sama閱讀 47,693評論 2 368
  • 正文 我出身青樓赁濒,卻偏偏與公主長得像,于是被迫代替她去往敵國和親孟害。 傳聞我的和親對象是個殘疾皇子拒炎,可洞房花燭夜當晚...
    茶點故事閱讀 44,577評論 2 353

推薦閱讀更多精彩內(nèi)容