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

xiongzenghui 發(fā)布于2019-07-01 11:01 / 3080人閱讀

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

首發(fā)于 樊浩柏科學院

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

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

背景描述

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

問題分析 確定輸入值

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

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

數(shù)組元素都為非負數(shù)，但可能為 0；

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

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

尋找規(guī)律

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

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

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

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

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

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

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

實現(xiàn)思路

經(jīng)過上述分析，問題規(guī)律已經(jīng)掌握清楚，這里整理出實現(xiàn)的思路。

整體思路

確定使用排序算法實現(xiàn)；

與傳統(tǒng)排序不同之處為元素之間的比較規(guī)則；

排序過程

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

比較規(guī)則

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

編碼實現(xiàn) 比較規(guī)則

/**
 * 比較規(guī)則
 * @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   待排序數(shù)組
 * @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;
}

/**
 * 尋找非零元素數(shù)組中所有元素排列組合后的最大值
 * @param   array     $Arr        待排序數(shù)組
 * @param   string    $method     排序方法
 * @return  mixed
 */
function array_form_max_str(array $Arr, $method = "bubble") {
    //參數(shù)校驗
    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 排序函數(shù)采用快速排序算法，這里直接使用之。

/**
 * 尋找非零元素數(shù)組中所有元素排列組合后的最大值
 * @param   array     $Arr        待排序數(shù)組
 * @param   string    $method     排序方法
 * @return  mixed
 */
function array_form_max_str(array $Arr, $method = "quick") {
    //參數(shù)校驗
    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 "數(shù)組為[", implode(",", $Arr), "]", PHP_EOL;
echo "最大排列組合為：", array_form_max_str($Arr), PHP_EOL;

測試結果

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

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

寫在最后

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

相關文章 ?

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

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

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

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

JavaScript || 數(shù)組

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

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

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

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

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

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

摘要：文章為原創(chuàng)首發(fā)地址描述給出一組非負整數(shù)，重新排列他們的順序把他們組成一個最大的整數(shù)。算法每個元素逐個字符進行對比。代碼代碼測試以上代碼已放到的上開源，歡迎或提建議。運行即可以測試。文章為原創(chuàng)首發(fā)地址：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中的數(shù)組

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

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