程序員面試題精選100題(41)-把數組排成最小的數(算法)

時間:2019-09-22 編輯:范文亭

題目:輸入一個正整數數組,將它們連接起來排成一個數,輸出能排出的所有數字中最小的一個。例如輸入數組{32,  321},則輸出這兩個能排成的最小數字32132請給出解決問題的算法,并證明該算法。

分析:這是096月份百度新鮮出爐的一道面試題,從這道題我們可以看出百度對應聘者在算法方面有很高的要求。

這道題其實是希望我們能找到一個排序規則,根據這個規則排出來的數組能排成一個最小的數字。要確定排序規則,就得比較兩個數字,也就是給出兩個數字mn,我們需要確定一個規則mn哪個更大,而不是僅僅只是比較這兩個數字的數值哪個更大。

根據題目的要求,兩個數字mn排成的數字mnnm,如果mn<nm,那么我們應該輸出mn,也就是m應該排在n的前面,也就是m小于n;反之,如果nm<mnn小于m。如果mn==mnm等于n

接下來我們考慮怎么去拼接數字,即給出數字mn,怎么得到數字mnnm并比較它們的大小。直接用數值去計算不難辦到,但需要考慮到的一個潛在問題是m

本文已影響
相關文章
大亨pk10计划苹果版