求非負元素數組所有元素能組合的最大字符串

xiongzenghui 發布于2019-07-01 11:01 / 3058人閱讀

摘要：尋找非零元素數組中所有元素排列組合后的最大值待排序數組排序方法參數校驗排序算法快速排序冒泡排序拼接用例測試這里只對快速排序方法使用組測試用例并列舉如下。

首發于 樊浩柏科學院

問題敘述：將一個非負元素數組中的所有元素排列組合在一起，找出值最大的那個排列情況。例如 [0, 9, 523, 94, 10, 4]，排列組合后值最大數為：9945234100。

本文廢話較多，可以直接跳轉到編碼實現部分。

背景描述

這是我遇到的一道筆試題。首次遇見我也是很懵，當時我的第一感覺就是排序，但是沒有及時理清里面的規律，導致后面并沒有解答出此題。

問題分析 確定輸入值

該問題描述很簡單，也給出了測試用例，需求很明白。但是還需要注意問題背后隱藏的一些問題。

可確定輸入的情況大致為：

數組元素都為非負數，但可能為 0；

數組長度并沒有確定，長度可能很大。這里假設操作不溢出；

數組元素的位數不確定，用例只涉及到 2 位數，需要考慮多位數的情況。這里假設操作不溢出；

尋找規律

面試時請教了一下面試官，面試官的思路：

最簡單辦法就是枚舉所有可能的排列組合情況，然后求排列組合后的最大值；再就是尋找組合的規律，滿足什么條件的元素排列在前。

當然這只是面試官提供的一些解決思路，付諸于實踐還需要探索。在復試前的一天晚上我再次翻出這個問題，并找到了一些思路。

就拿問題中的用例 [0, 9, 523, 94, 10, 4] 來說，需要找出的結果為：9,94,523,4,10,0（為了方便說明，用”,“分割了數組元素）。

先將復雜問題簡單化處理，首先嘗試使用 排序算法 來分析過程。分析 9 和 94 的排列，為什么 9 排列在 94 前？[那是因為這 2 個數存在 2 種排列情況，既_ 9_94_ 和_ 9_49_，很明顯 9_94 排列大于 9_49 排列，所以需要將 9 排列在 94 前，反之則需要交換元素位置]()。如果采用這樣規則處理，是在 2 個元素之間進行枚舉排列情況，且單次枚舉情況限定在了 2 種，降低了問題的復雜程度并易于編碼實現，后續可以直接使用排序方法來多次重復這種 2 個元素之間的單次枚舉動作。

說明：符號“_”為占位符，表示該位置可能還存在其他元素，但不影響當前兩個元素的前后排列順序。后續出現該符號將不再說明。

總之，我認為該問題是排序問題的一個變種情況，同排序問題不同的是 比較規則。這里不是直接比較 2 個元素值大小，而是比較 2 個元素排列組合后值的大小。

實現思路

經過上述分析，問題規律已經掌握清楚，這里整理出實現的思路。

整體思路

確定使用排序算法實現；

與傳統排序不同之處為元素之間的比較規則；

排序過程

使用冒泡排序來說明上述用例的排序過程。

比較規則

本問題的排序比較規則可以描述為：假設參與比較的兩個元素為 A、B（初始時 A 在 B 前，排序結果從左至右為由大到小），比較時如果排列 A_B 小于排列 _B_A_，A 和 B 則交換位置，反之不交換。

編碼實現 比較規則

/**
 * 比較規則
 * @param   string    $a
 * @param   string    $b
 * @return  int
 */
function cmp($a, $b) {
    if ($a == $b) {
        return 0;
    }
    return $a . $b > $b . $a ? -1 : 1;
}

冒泡排序

/**
 * 冒泡排序
 * @param   array    $Arr   待排序數組
 * @return  array
 */
function bubble_sort(array $Arr) {
    $length = count($Arr);
    if ($length < 2) {
        return $Arr;
    }

    for ($i = 1, $change = true; $i <= $length && $change; $i++) {
        $change = false;
        for ($j = $length - 1; $j > $i - 1; $j--) {
            if (cmp($Arr[$j - 1], $Arr[$j]) > 0) {
                $temp = $Arr[$j - 1];
                $Arr[$j - 1] = $Arr[$j];
                $Arr[$j] = $temp;
                $change = true;
            }
        }
    }
    return $Arr;
}

/**
 * 尋找非零元素數組中所有元素排列組合后的最大值
 * @param   array     $Arr        待排序數組
 * @param   string    $method     排序方法
 * @return  mixed
 */
function array_form_max_str(array $Arr, $method = "bubble") {
    //參數校驗
    if (!is_array($Arr)) return false;
    foreach ($Arr as $value) {
        if ($value < 0) return false;
    }
    //排序算法
    switch ($method) {
        case "quick" :
            usort($Arr, "cmp");           //快速排序
            break;
        case "bubble" :
            $Arr = bubble_sort($Arr);     //冒泡排序
            break;
        default : break;
    }
    //拼接
    return implode("", $Arr);
}

快速排序

由于 PHP 中 sort 排序函數采用快速排序算法，這里直接使用之。

/**
 * 尋找非零元素數組中所有元素排列組合后的最大值
 * @param   array     $Arr        待排序數組
 * @param   string    $method     排序方法
 * @return  mixed
 */
function array_form_max_str(array $Arr, $method = "quick") {
    //參數校驗
    if (!is_array($Arr)) return false;
    foreach ($Arr as $value) {
        if ($value < 0) return false;
    }
    //排序算法
    switch ($method) {
        case "quick" :                   //快速排序
            usort($Arr, "cmp");
            break;
        case "bubble" :
            $Arr = bubble_sort($Arr);    //冒泡排序
            break;
        default : break;
    }
    //拼接
    return implode("", $Arr);
}

用例測試

這里只對快速排序方法使用 2 組測試用例并列舉如下。

測試代碼

$Arr = [20,913,223,91,20,3];
echo "數組為[", implode(",", $Arr), "]", PHP_EOL;
echo "最大排列組合為：", array_form_max_str($Arr), PHP_EOL;

測試結果

//第1組用例
數組為[0,9,523,94,10,4]
最大排列組合為：9945234100

//第2組用例
數組為[20,913,223,91,20,3]
最大排列組合為：9191332232020

寫在最后

經過深入分析問題的本質，也使得我對與排序算法有了更深入的認識，更算是一個鞏固。同時，正是由于我嘗試著去解決這個問題，才使得我在后面的復試環節中面試官再次提出相同問題時，給出了一個滿意的解決方案。

相關文章 ?

王者編程大賽之一（2017-12-05）

云服務器 GPU云服務器求非負 php去除數組的元素所有元素 html5 所有元素

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/29740.html

JavaScript || 數組

摘要：總結使用訪問數組元素，使用訪問數組屬性，如。數組的長度保證大于每個元素的索引值，數組沒有元素，最大索引為，為為數組元素賦值，如果其索引大于等于現有數組長度，的屬性值將設置為如果設置的值小于數組長度時，會將索引大于的元素全部刪除。數組數組是值的有序集合，數組中每個值稱為元素，元素在數組中的位置稱為索引。JavaScript中的數組是一種特殊的對象：類屬性class attribu...

Euphoria 2019-08-20 14:42 評論0 收藏0
犀牛書——CHAP7：數組

摘要：數組有以下特點無類型數組元素可以是任意元素。因此，當小于數組最大索引時，大于的數組元素會被刪除。原數組不會改變將數組元素轉換為字符串并連接在一起。默認將數組元素用，連接，傳入的參數即為連接符。 showImg(https://box.worktile.com/view/fcfcdf2c99b14edfb6768085955ae253?pid=4b0845b09ca94218a955f8...

Alfred 2019-08-19 18:40 評論0 收藏0
JavaScript數據結構與算法-Array-(leetcode原題)

摘要：的最大公約數是，記為，，。示例輸入輸出示例輸入輸出注意數組內已種好的花不會違反種植規則。輸入的數組長度范圍為。是非負整數，且不會超過輸入數組的大小。博客原文地址： https://finget.github.io/2019... 只出現一次的數字i 給定一個非空整數數組，除了某個元素只出現一次以外，其余每個元素均出現兩次。找出那個只出現了一次的元素。說明：你的算法應該具有線...

joy968 2019-08-26 13:51 評論0 收藏0
給出一組非負整數，重新排列他們的順序把他們組成一個最大的整數。

摘要：文章為原創首發地址描述給出一組非負整數，重新排列他們的順序把他們組成一個最大的整數。算法每個元素逐個字符進行對比。代碼代碼測試以上代碼已放到的上開源，歡迎或提建議。運行即可以測試。文章為原創首發地址：https://hooyes.net/p/python-l... showImg(https://segmentfault.com/img/bV8gIs?w=976&h=140); 描...

VincentFF 2019-07-30 16:09 評論0 收藏0
javascript中的數組

摘要：例如返回是返回是的前兩個參數制定了需要刪除數組元素。注意一旦和確認該返回什么值它們就會停止遍歷數組元素。和和方法使用指定的函數將數組元素進行組合，生成單個值。數組是值的有序集合。每個值叫做一個元素，而每個元素在數組中有一個位置，以數字表示，稱為索引。javascript的數組是無類型的：數組元素可以是任意類型，并且同一個數組中的不同元素也可能有不同的類型。一創建數組使用數組直接...

xinhaip 2019-08-19 18:26 評論0 收藏0