• 最小的k個(gè)數(shù)
• 求子數(shù)組的最大和
• 把數(shù)組排成最小的數(shù)字

1.最小的k個(gè)數(shù)

問(wèn)題描述：輸入n個(gè)數(shù)字，找到數(shù)組中最小的k個(gè)數(shù)谭羔。例如輸入4,5,1,6,2,7,3,8這8個(gè)數(shù)字，最小的4個(gè)數(shù)字就是1,2,3,4夯膀。

算法思想

思路一：我們可能會(huì)有這樣一個(gè)思路，先對(duì)數(shù)組進(jìn)行排序日裙，這樣找最小的k個(gè)數(shù)字就簡(jiǎn)單多了，但是排序的時(shí)間復(fù)雜度是O(nlogn)惰蜜。我們可以嘗試快速排序的思路昂拂，快速排序是每次找到一個(gè)數(shù)字，對(duì)數(shù)組中的數(shù)字抛猖，比這個(gè)數(shù)字小的排在前面格侯，比這個(gè)數(shù)字大的排在后面。那么我們?nèi)绻槍?duì)第k個(gè)數(shù)字進(jìn)行調(diào)整财著，比這個(gè)數(shù)字小的排前面联四，比這個(gè)數(shù)字大的排后面，那么最后排在前面的k個(gè)數(shù)字就是我們要找的數(shù)字了瓢宦，這個(gè)算法的時(shí)間復(fù)雜度是O(n).

這樣的思路我們需要清楚兩點(diǎn)：首先碎连，這個(gè)算法會(huì)改變?cè)瓉?lái)數(shù)組的順序，因?yàn)楸緛?lái)就是基于快速排序的驮履。其次鱼辙，我們最后得到的這k個(gè)數(shù)字是無(wú)序的。

思路二：時(shí)間復(fù)雜度為O(nlogk)的算法玫镐。
我們先定義好一個(gè)長(zhǎng)度為k個(gè)容器倒戏，每次從輸入的數(shù)組中選擇一個(gè)數(shù)字填入這個(gè)容器中，如果容器沒(méi)有滿恐似，那么直接將讀到的數(shù)字填入其中杜跷，如果容器滿了，那么從容器中選擇最大的數(shù)字矫夷，和這個(gè)數(shù)字比較葛闷，如果它比讀到的數(shù)字大，就替換掉這個(gè)最大的數(shù)字双藕，否則就讀下一個(gè)淑趾。

當(dāng)容器滿了之后，我們需要做3件事情忧陪，第一扣泊，找到容器中最大的數(shù)字；第二嘶摊，有可能刪除這個(gè)最大的數(shù)字延蟹；第三，可能插入一個(gè)數(shù)字叶堆。

如果我們用二叉樹實(shí)現(xiàn)這個(gè)容器阱飘，那么我們能在O(logk)內(nèi)完成這3步操作。對(duì)于n個(gè)輸入的數(shù)字而言，時(shí)間復(fù)雜度就是O(nlogn)俯萌。我們可以用不同的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)這個(gè)二叉樹果录，比如說(shuō)大頂堆，這樣我們能在O(1)時(shí)間內(nèi)找到最大的數(shù)字咐熙，但是刪除和插入結(jié)點(diǎn)還是需要O(logk)。也可以借助紅黑樹來(lái)實(shí)現(xiàn)辨萍。這里只寫了個(gè)思路棋恼，有興趣的同學(xué)可以自己嘗試一下。

在提一點(diǎn)锈玉，這一種思路很適合處理海量數(shù)據(jù)爪飘，它不會(huì)改變?cè)瓟?shù)組的順序，每次讀入一個(gè)數(shù)字拉背，當(dāng)原數(shù)據(jù)很大的時(shí)候师崎，不能完全加載如內(nèi)存，每次讀取一個(gè)數(shù)字就很有優(yōu)勢(shì)椅棺，所以對(duì)于n很大犁罩，而k很小的時(shí)候，這一種思路更好两疚。

代碼

這里實(shí)現(xiàn)的思路一的代碼床估，后面有時(shí)間我再補(bǔ)上思路二的代碼。

//交換a,b兩個(gè)指針指向元素的位置
void Swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

//找最后一個(gè)數(shù)字進(jìn)行比較,比它小的排前面诱渤，比它大的排后面
int Partition(int *data, int length, int start, int end)
{
    if (data == NULL || length < 0 || start < 0 ||
        end >= length)
    {
        fprintf(stderr, "Invalid parameter.\n");
        exit(1);
    }

    int small = start - 1;//small下標(biāo)要比start小

    for (int index = start; index < end; index++)
    {
        if (data[index] < data[end])//比它小的放前面
        {
            small++;
            if (small != index)
                Swap(&data[small], &data[index]);
        }
    }
    Swap(&data[++small], &data[end]);
    return small;//返回分割點(diǎn)丐巫，start~small是<=data[end]的數(shù)
}

//基于快速排序思路的算法
/*data :輸入的數(shù)組  length：輸入數(shù)組的長(zhǎng)度
  output:輸出數(shù)組   k：最小的k個(gè)數(shù)
*/
void GetLeastNumbers_1(int data[], int length, int *output, int k)
{
    if(data == NULL || output == NULL || length <= 0 
    || k <= 0 || k > length)
    {
        fprintf(stderr, "Invalid parameter!\n");
        exit(1);
    }
    int start = 0;
    int end = length - 1;
    int index = Partition(data, length, start, end);//找到分割點(diǎn)
    while (index != k -1)
    {
        if (index < k - 1)
            start = index + 1;
        esle
            end = index - 1;
    
        index = Partition(data, length, start, end);
    }

    for (int i = 0; i < k; i++)
    {
    output[i] = data[i];
    }
}

其實(shí)看了上面的代碼我們會(huì)發(fā)現(xiàn)，這個(gè)算法并不是絕對(duì)的O(n)的時(shí)間復(fù)雜度勺美，可以確定的是Partition函數(shù)的時(shí)間復(fù)雜度為O(n)递胧，計(jì)算分割點(diǎn)時(shí)，我們可以發(fā)現(xiàn)赡茸，如果分割點(diǎn)不是k-1缎脾，那么還需要下一次計(jì)算，最壞的情況下坛掠，如果k大于length/2,且每次計(jì)算的index只是遞增1赊锚，那么時(shí)間復(fù)雜度就會(huì)增加到O(n^2),基于快速排序的的算法時(shí)間復(fù)雜度受選取的這個(gè)數(shù)字的影響很大，如果這個(gè)數(shù)字恰好就是第k大的數(shù)字屉栓，那么我們能在O(n)內(nèi)解決這個(gè)問(wèn)題舷蒲。

2.求子數(shù)組的最大和

問(wèn)題描述：輸入一個(gè)整數(shù)數(shù)組，數(shù)組中有正數(shù)也有負(fù)數(shù)友多，數(shù)組中連續(xù)的一個(gè)或多個(gè)數(shù)字組成該數(shù)組的子數(shù)組牲平，求子數(shù)組的最大和。例如：數(shù)組{1,-2,3,10,-4,7,2,-5},最大子數(shù)組是{3,10,-4,7,2},和是18.

算法思想

思路一：我們分析一下這個(gè)數(shù)組找到子數(shù)組的最大和過(guò)程域滥。step1纵柿，step2蜈抓，我們加上數(shù)字1和-2，得到當(dāng)前的和是-1昂儒；step3沟使，定位到3，這是之前的和是-1渊跋，加上3之后是2腊嗡，還小于3，所以之前的和就舍棄拾酝，直接從3開始往后加燕少；step4,繼續(xù)加10，和為13蒿囤；step5客们，遇到-4，加上-4之后材诽，和是-9底挫，反而變小了，這里我們需要保存一下13岳守，可能它就是最大的和凄敢；step6，遇到7湿痢，這時(shí)和是9+7=16涝缝，比13大，修改這個(gè)保存的值譬重；step7拒逮，遇到2，此時(shí)和為16+2=18臀规，修改保存的值滩援；step8，遇到-5塔嬉，和變成了13玩徊，所以舍棄這個(gè)數(shù)字，最后的結(jié)果是18.

總結(jié)一下谨究，就是在加下一個(gè)數(shù)字的時(shí)候恩袱，保存下當(dāng)前的最大和，當(dāng)之前計(jì)算的和是負(fù)數(shù)的時(shí)候胶哲，做一下處理畔塔，直接舍棄，從當(dāng)前數(shù)字開始計(jì)算。

思路二：用動(dòng)態(tài)規(guī)劃法的思路來(lái)解決問(wèn)題澈吨，動(dòng)態(tài)規(guī)劃法的思想就是將問(wèn)題分解問(wèn)多個(gè)子問(wèn)題求解把敢，由子問(wèn)題的解得到問(wèn)題的解，與分治法不同的是谅辣，它的子問(wèn)題之間不是獨(dú)立的修赞，當(dāng)前子問(wèn)題的解需要借助上一次求解的結(jié)果，這就是我們說(shuō)的重疊子問(wèn)題桑阶。

分析題目我們可以得到遞歸公式榔组，公式中的f(i)表示當(dāng)前計(jì)算得到的和，那么max(f(i))就是我們要找的子數(shù)組的最大和联逻。

遞歸公式

我們基于循環(huán)來(lái)實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃法，其實(shí)和上面的算法的代碼是一樣的检痰，只是分析思路不同而已包归。

代碼

//計(jì)算子數(shù)組的最大和
int FindGreatestSumOfSubArray(int data[], int length)
{
    if (data == NULL || length <= 0)
    {
        fprintf(stderr, "Invalid parameter!\n");
        exit(1);
    }

    int currentSum = 0;
    //greatest初始化為數(shù)組中的數(shù)字，否則當(dāng)數(shù)組全是負(fù)數(shù)的時(shí)候就會(huì)出錯(cuò)
    int greastSum = data[0];
    for (int i = 0; i < length; i++)
    {
        if (currentSum < 0)
            currentSum = data[i];
        else
            currentSum += data[i];//在上一次求和的基礎(chǔ)上加上當(dāng)前的數(shù)字
        if(currentSum > greastSum)
            greastSum = currentSum;
    }
    return greastSum;
}

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

問(wèn)題描述：輸入一個(gè)整數(shù)數(shù)組铅歼，將數(shù)組中的數(shù)字拼接公壤，排成一個(gè)數(shù)字，打印出所能排出的最小的數(shù)字椎椰。例如厦幅，數(shù)組{3,32,321}，則這三個(gè)數(shù)字排出的數(shù)字中最小的數(shù)字是321323.

算法思想：

思路一：遇到這個(gè)題慨飘，我們可能會(huì)想到字符串的全排列确憨，在之前的算法系列的文章中有提到過(guò)，如果找出其全排列瓤的，再比較得到最小的休弃，那么時(shí)間復(fù)雜度為O(n!)，這樣的算法思想明顯是不好的圈膏。
思路二:考慮另一種思路塔猾，將數(shù)組排成最小的數(shù)字，其實(shí)就是找到一個(gè)排序規(guī)則稽坤，假如有n,m兩個(gè)數(shù)字丈甸，可以排成nm,mn，我們需要考慮是nm這樣的順序數(shù)字小還是mn這樣的順序得到的數(shù)字小尿褪，這里的比較規(guī)則不再是n和m哪個(gè)數(shù)字小睦擂， 而是比較組合之后的結(jié)果哪個(gè)更小,如果是針對(duì)數(shù)字進(jìn)行這樣的比較，我們需要從數(shù)字的最高位一位一位比較茫多。

接下來(lái)考慮拼接數(shù)字n和m是int型數(shù)據(jù)祈匙，但是不能保證nm還是int型的，也許拼接之后它就超出了int的表示范圍，而題目也沒(méi)有要求我們返回一個(gè)數(shù)字夺欲，所以跪帝，可以考慮將數(shù)字轉(zhuǎn)換為字符串表示，這樣我們就可以使用字符串的拼接函數(shù)了和比較函數(shù)些阅，而不用針對(duì)數(shù)字的每一位進(jìn)行比較伞剑，這樣會(huì)簡(jiǎn)單許多。

由以上分析得出思路：先將整數(shù)數(shù)組轉(zhuǎn)換為字符串市埋，然后定義比較函數(shù)黎泣，對(duì)字符串進(jìn)行排序，最后輸出字符串缤谎，其中比較函數(shù)是關(guān)鍵（定義比較函數(shù)時(shí)要注意抒倚，字符串n和m的比較結(jié)果和nm和mn的比較結(jié)果是有很大差異的）。

代碼

代碼中可以直接使用系統(tǒng)的排序函數(shù)坷澡，c語(yǔ)言中是qsort托呕。由于我個(gè)人更熟悉Java，這里用了Java實(shí)現(xiàn)频敛，直接調(diào)用了Java中的排序函數(shù)项郊。

//用MyArray調(diào)用靜態(tài)方法
public class MyArray {

    public static void printMinNumber(int numbers[]) {
        if(numbers == null)
            return;
        //將整數(shù)數(shù)組轉(zhuǎn)換為字符串
        String[] strNumbers = new String[numbers.length];
        for(int i = 0; i < numbers.length; i++) {
            strNumbers[i] = String.valueOf(numbers[i]);
        }
    
        //調(diào)用排序算法TimSort
        Arrays.sort(strNumbers, new StringCompator());
    
        System.out.println(getString(strNumbers));
    }

    //將字符串?dāng)?shù)字轉(zhuǎn)為字符串
    private static String getString(String strs[]) {
        StringBuilder sBuilder = new StringBuilder();
        for (String str : strs){
            sBuilder.append(str);
        }
        return sBuilder.toString();
    }   
}

定義比較器。

public class StringCompator implements Comparator<String> {

    @Override
    public int compare(String str1, String str2) {
        String temp1 = new String(str1);
        String temp2 = new String(str2);
    
        temp1 = temp1.concat(str2);
        temp2 = temp2.concat(str1);
        //比較組合之后的字符串的大小
        return temp1.compareTo(temp2);
    }
}

時(shí)間復(fù)雜度分析：由于我使用了Java實(shí)現(xiàn)斟赚，Java7之后着降，內(nèi)置的排序函數(shù)就默認(rèn)為TimSort，它是歸并排序和插入排序的組合拗军，在待排數(shù)組有一定順序的情況下任洞，可以達(dá)到O(n)的時(shí)間復(fù)雜度，在隨機(jī)的情況下也可以達(dá)到O(nlogn)食绿，所以最后的時(shí)間復(fù)雜度是O(nlogn)侈咕，比第一種思路要好很多。

總結(jié)

這次就到這里了器紧，數(shù)組部分后面還會(huì)有一篇耀销。不足之處，還請(qǐng)多指教铲汪。