數(shù)組

記錄《劍指offer》中所有關(guān)于數(shù)組的題目，以及LeetCode中的相似題目

相關(guān)題目列表

• 說明 由于簡(jiǎn)書中的markdown不支持錨點(diǎn)，所以無(wú)法生成目錄進(jìn)行頁(yè)內(nèi)跳轉(zhuǎn)，文章較長(zhǎng)，如果需要閱讀單一題目，只能ctrl+f 嘍。

題目

數(shù)組是最簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，其占據(jù)一塊連續(xù)內(nèi)存，在C++標(biāo)準(zhǔn)庫(kù)STL中array表示數(shù)組，但是array在實(shí)際中應(yīng)用的并不多，我們一般使用更全能的vector代替，可以簡(jiǎn)單講array理解為vector<int>。

面試題3. 二維數(shù)組中的查找

題目：在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請(qǐng)完成一個(gè)函數(shù)，輸入這樣一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)。

題目分析

如書中所給示例：
在下面矩陣中，查找數(shù)字5

矩陣示例

首先選取數(shù)組中右上角的數(shù)字<9>。如果該數(shù)字等于要查找的數(shù)字，查找過程結(jié)束；如果該數(shù)字大于要查找的數(shù)字，剔除這個(gè)數(shù)字所在的列<9,12,13,15>（因?yàn)檫@一列必定都大于所要查找的數(shù)字）；如果該數(shù)字小于要查找的數(shù)字，剔除這個(gè)數(shù)字所在的行（因?yàn)檫@一行必定都大于要查找的數(shù)字）。

也就是說如果要查找的數(shù)字不在數(shù)組的右上角，則每一次都在數(shù)組的查找范圍中剔除一行或者一列，這樣每一步都可以縮小查找的范圍，知道找到要查找的數(shù)字，或者查找范圍為空。

參考代碼

#include<iostream>
#include<vector>

using namespace std;

bool Find(int *matrix, int m, int n, int key)
{
    bool result = false;
    if (matrix != NULL && m > 0 && n > 0)
    {
        int row = 0;    //初始化所在行為第一行
        int column = n - 1;     //初始化所在列為最后一列，從而鎖定右上角

        while (row < m && column > 0)
        {
            if (matrix[row * n + column] == key)    //matrix為右上角位置
            {
                result = true;
                break;
            }
            else if (matrix[row * n + column] > key)
                --column;       //所在列遞減表明向左移動(dòng)
            else
                ++row;  //所在行遞增，表明逐漸向下移動(dòng)
        }
    }
    return result;
}

//=====================測(cè)試樣例=====================

void Test1()
{
    int m, n, key;
    int *matrix;

    cin >> m >> n >> key;
    //cout << endl;
    for (int i = 0; i < m * n; ++i)
    {
        cin >> matrix[i];
    }

    if (Find(matrix, m, n, key))
        cout << "true" << endl;
    else
        cout << "false" << endl;
}

int main()
{
    Test1();

    return 0;
}

上面的代碼是通過指針來(lái)表示一個(gè)二維數(shù)組的，也可以通過vector<vector<int>> 來(lái)表示一個(gè)數(shù)組，用同樣的方法完成題目。代碼示例如下：

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty())
            return false;
        bool res = false;
        int m = matrix.size();
        int n = matrix[0].size();

        int row = 0;
        int col = n - 1;
        while (row < m && col >= 0) {
            if (matrix[row][col] == target)
                return true;
            else if (matrix[row][col] > target) {
                --col;
            }
            else if (matrix[row][col] < target) {
                ++row;
            }
        }
        return res;
    }
};

相似題目

本題與LeetCode中的240. Search a 2D Matrix II完全一致，另外LeetCode中還有一道同為二維數(shù)組查找的題目74. Search a 2D Matrix。
下面是這兩道題的參考代碼：
LeetCode 240 code
LeetCode 74 code

除LeetCode外，也可以在?？途W(wǎng) 劍指offer上完成本題。

面試題8. 旋轉(zhuǎn)數(shù)組的最小數(shù)字

題目：把一個(gè)數(shù)組最開始的若干個(gè)元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。輸入一個(gè)遞增排序的數(shù)組的一個(gè)旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。例如數(shù)組{3,4,5,1,2}為{1,2,3,4,5}的一個(gè)旋轉(zhuǎn)，該數(shù)組的最小值為1。

題目分析

這道題最直觀的做法就是直接遍歷數(shù)組找出最小值，時(shí)間復(fù)雜度為O(n)，但是這樣就沒有完全利用題目中旋轉(zhuǎn)數(shù)組的條件。所以我們要想得到更高效的解決方法就需要在旋轉(zhuǎn)數(shù)組中找到突破口。

參考代碼

#include<iostream>

using namespace std;

//遍歷數(shù)組，得到最小值
int MinInOrder(int *numbers, int index1, int index2)
{
    int result = numbers[index1];
    for (int i = index1 + 1; i <= index2; ++i)
    {
        if (numbers[i] < result)
            result = numbers[i];
    }

    return result;
}

int Min(int *numbers, int length)
{
    int index1 = 0;
    int index2 = length - 1;
    int MidIndex = index1;  //當(dāng)不滿足while循環(huán)條件時(shí)，證明數(shù)組本身有序，直接返回第一個(gè)元素，即是最小元素

    if (numbers == NULL || length <= 0)
        return -1;

    while (numbers[index1] >= numbers[index2])    //一般情況下旋轉(zhuǎn)數(shù)組的特性
    {
        if (index1 == index2 - 1)    //循環(huán)中止條件
        {
            MidIndex = index2;
            break;
        }

        MidIndex = (index1 + index2)/2;

        //如果三個(gè)指針位置數(shù)值大小相等，則無(wú)法確定中間位置屬于遞增部分還是遞減部分，只能采用遍歷方式
        if (numbers[index1] == numbers[MidIndex] && numbers[index1] == numbers[index2])
            return MinInOrder(numbers, index1, index2);


        if (numbers[MidIndex] >= numbers[index1])
            index1 = MidIndex;
        else if (numbers[MidIndex] <= numbers[index2])
            index2 = MidIndex;
    }

    return numbers[MidIndex];
}

void test1()    //一般測(cè)試樣例
{
    int numbers[] = {3,4,5,1,2};
    cout << Min(numbers, 5) << endl;
}

void test2()    //測(cè)試樣例2，測(cè)試全部相等的數(shù)
{
    int numbers[] = {1,1,1,1,1};
    cout << Min(numbers, 5) << endl;
}

void test3()    //測(cè)試樣例3，測(cè)試index1， index2， MidIndex 相等
{
    int numbers[] = {1,0,1,1,1};
    cout << Min(numbers, 5) << endl;
}

void test4()
{
    int numbers[] = {1,2,3,4,5};
    cout << Min(numbers, 5);
}

int main()
{
    test1();
    test2();
    test3();
    test4();

    return 0;
}

參考代碼中是以指針的形式表示數(shù)組，同樣也可以以vector<int>的方式。
因?yàn)榇a中都帶有詳細(xì)的注釋，所以如果不是特別復(fù)雜的邏輯結(jié)構(gòu)，都直接以代碼的形式展示題解。Just Show Me Your Code！

相似題目

本題與LeetCode中的153. Find Minimum in Rotated Sorted Array完全一致?？梢栽谏厦孢M(jìn)行代碼驗(yàn)證。
另外，LeetCode中還有本題中關(guān)于數(shù)組旋轉(zhuǎn)的題目189. Rotate Array
下面是LeetCode中兩道題的參考代碼：
LeetCode 153 code
LeetCode 189 code

除LeetCode外也可以在牛客網(wǎng) 劍指offer中完成本題。

題目14. 調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)之前

題目：輸入一個(gè)整數(shù)數(shù)組，實(shí)現(xiàn)一個(gè)函數(shù)來(lái)調(diào)整該數(shù)組中數(shù)字的順序，使得所有奇數(shù)位于數(shù)組的前半部分，所有偶數(shù)位于數(shù)組的后半部分。

題目分析

數(shù)組示例

對(duì)于這道題，很容易想到的方法是維護(hù)兩個(gè)指針left，right，分別指向數(shù)組的首尾位置，采用雙向遍歷的方式，如果left指向的元素為偶數(shù)，且right指向的元素為奇數(shù)，則交換兩個(gè)元素。直到遍歷玩整個(gè)數(shù)組，即可滿足條件。參考代碼如1。

值得注意的是，對(duì)于這道題，存在擴(kuò)展性的解法，因?yàn)轭}目要求是區(qū)分奇偶數(shù)，這只是這類問題的一個(gè)特例，我們也可以通過傳入函數(shù)的指針形式，完成這類問題的擴(kuò)展性解法。參考代碼如2。

參考代碼

cpp1

#include<iostream>
#include<vector>

using namespace std;

class Solution
{
public:
    void ReorderArray(vector<int>& nums)
    {
        int start = 0;
        int end = nums.size() - 1;

        while (start < end)
        {
            while (nums[start] % 2 == 1)
                start++;
            while (nums[end] % 2 == 0)
                end--;

            if (start < end)
                Swap(&nums[start], &nums[end]);
        }
    }
private:
    void Swap(int* i, int* j)
    {
        int temp;
        temp = *i;
        *i = *j;
        *j = temp;
    }
};

cpp2

/*=============將函數(shù)寫成模式=================*/
void Swap(int* i, int* j)
{
    int temp = *i;
    *i = *j;
    *j = temp;
}

void Recorder(vector<int>& nums, bool (*func)(int))
{
    if(nums.empty())
        return;

    int start = 0;
    int end = nums.size() - 1;
    while (start < end)
    {
        while (!func(nums[start]))
            start++;
        while (func(nums[end]))
            end--;

        if (start < end)
            Swap(&nums[start], &nums[end]);
    }
}

bool isEven(int n)
{
    return (n % 2 == 0);
}

void RecorderOddEven(vector<int> &nums)
{
    Recorder(nums, isEven);
}

相似題目

可以在?？途W(wǎng) 劍指offer上完成對(duì)本題的驗(yàn)證。

面試題20： 順時(shí)針打印矩陣

題目：輸入一個(gè)矩陣，按照從外向里以順時(shí)針的順序依次打印出每一個(gè)數(shù)字。例如，如果輸入如下矩陣：

矩陣示例

則依次打印出數(shù)字1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16。

題目分析

這道題并沒有復(fù)雜的數(shù)據(jù)結(jié)構(gòu)和算法分析，主要考察的是對(duì)邊界條件的控制，這需要通過實(shí)例慢慢驗(yàn)證。
打印第一圈的左上角的坐標(biāo)是(0,0)，第二圈的左上角的坐標(biāo)是(1,1)，依次類推。我們注意到，左上角的坐標(biāo)中行和列總是相同的，可以在矩陣中選取左上角為(start,start)的一圈作為我們分析的目標(biāo)。
這道題沒有涉及復(fù)雜的數(shù)據(jù)結(jié)構(gòu)和高級(jí)的算法，看起來(lái)是一個(gè)簡(jiǎn)單的問題，但是要解決這個(gè)問題，會(huì)在代碼中包含多個(gè)循環(huán)，并且還需要判斷多個(gè)邊界條件。
由于是以外圈到內(nèi)圈的順序依次打印，我們可以把矩陣想象成若干個(gè)圈。利用每次循環(huán)打印一個(gè)圈。
對(duì)于一個(gè)5×5的矩陣而言，最后一圈只有一個(gè)數(shù)字，對(duì)應(yīng)的坐標(biāo)是(2,2)，我們發(fā)現(xiàn)5>2×2。對(duì)于一個(gè)6×6的矩陣而言，最后一圈有4個(gè)數(shù)字，其左上角的坐標(biāo)仍然是2×2。同樣6＞2×2.于是我們可以得到循環(huán)繼續(xù)的條件時(shí)columns＞startX × 2并且rows＞ startY× 2。
接下來(lái)我們考慮如何實(shí)現(xiàn)打印一圈的功能。我們可以把打印一圈分為四步：第一步從左到右打印一行，第二步從上到下打印一列，第三步從右到左打印一行，第四部從下到上打印一列。
仔細(xì)分析打印時(shí)每一步的前提條件。第一步總是必須的。第二步的前提條件是終止行號(hào)大于起始行號(hào)。第三步的打印條件是起始列號(hào)小于終止列號(hào)，并且第二步條件也需要滿足。第四步的前提條件是終止行號(hào)比起始行號(hào)至少大2，同時(shí)終止列號(hào)大于起始列號(hào)。

參考代碼

#include<iostream>
#include<vector>

using namespace std;

class Solution {
public:
    void printMatrix(vector<vector<int> > matrix) {
        int rows = matrix.size();
        int columns = matrix[0].size();
        if (rows <= 0 && columns <= 0)
            return;

        int start = 0;
        while (rows > start * 2 && columns > start * 2){
            PrintACircle(matrix, start, rows, columns);
            start++;
        }
    }
private:
        void PrintACircle(vector<vector<int>> matrix, int start, int rows, int columns){
            int endX = rows - 1 - start;
            int endY = columns - 1 - start;

            for (int i = start; i <= endY; ++i){
                cout << matrix[start][i] << ",";
            }
            if (endX > start){
                for (int i = start + 1; i <= endX; ++i){
                    cout << matrix[i][endY] << ",";
                }
            }
            if (endX > start && endY > start){
                for (int i = endY - 1; i >= start; --i){
                    cout << matrix[endX][i] << ",";
                }
            }
            if (endX > start + 1 && endY > start){
                for (int i = endX - 1; i > start; --i){
                    cout << matrix[i][start] << ",";
                }
            }
        }
};

int main()
{
    vector<vector<int>> nums = { {1,2,3,4}, {5,6,7,8}, {9,10,11,12}, {13,14,15,16}};
    Solution solu;
    solu.printMatrix(nums);

    return 0;
}

相似題目

本題與LeetCode中的54. Spiral Matrix完全一致，可以在上面進(jìn)行驗(yàn)證。
此題參考代碼見：
LeetCode 54 code ??? 這里與參考代碼是不同的，以方便選擇自己認(rèn)為可讀性更好的代碼進(jìn)行閱讀。
還可以在?？途W(wǎng) 劍指offer上對(duì)編碼進(jìn)行驗(yàn)證。

面試題29： 數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字

題目： 數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長(zhǎng)度的一半，請(qǐng)找出這個(gè)數(shù)字。例如輸入一個(gè)長(zhǎng)度為9的數(shù)組{1,2,3,2,2,2,5,4,2}。由于數(shù)字2在數(shù)組中出現(xiàn)了5次，超過數(shù)組長(zhǎng)度的一半，因此輸出2。

題目分析

本題最容易想到的方法就是排序，排序數(shù)組的中間位置即為所求。
接下來(lái)思考是否還有效率更高的方法。由題目可知，該題就是找到數(shù)組中的中位數(shù)。即長(zhǎng)度為n的數(shù)組中第n/2大的數(shù)字。這屬于一類問題，統(tǒng)稱為Top-k問題。我們有成熟的算法完成此類問題。

參考代碼

基于partation的方法

class Solution {
public:
    /*
    //完全排序方式
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int middle = nums.size()/2;
        return nums[middle];
    }
    */

    //partation做法
    int majorityElement(vector<int>& nums) {
        int length = nums.size();
        int middle = length >> 1;
        int start = 0;
        int end = length - 1;
        int index = Partation(nums, start, end);

        //直到找到middle
        while (index != middle){
            if (index > middle){
                end = index - 1;
                index = Partation(nums, start, end);
            }
            else if (index < middle){
                start = index + 1;
                index = Partation(nums, start, end);
            }
        }
        return nums[middle];
    }
private:
    int Partation(vector<int>& nums, int start, int end){
        int small = start - 1;
        //int index = start;
        int temp = Random(start, end);
        //交換標(biāo)準(zhǔn)
        Swap(&nums[temp], &nums[end]);
        for (int i = start; i < end; ++i){
            if (nums[i] < nums[end]){
                ++small;
                if (small != i)
                    Swap(&nums[small], &nums[i]);
            }
        }
        ++small;
        Swap(&nums[small], &nums[end]);

        return small;
    }

    int Random(int start, int end){
        if (end > start)
            return start + rand() % (end - start);
        else
            return 0;
    }

    void Swap(int* i, int* j){
        int temp = *i;
        *i = *j;
        *j = temp;
    }
};

還可以采用堆或者紅黑樹的方法完成Top-k問題，這里在第30題中會(huì)介紹。

另外根據(jù)本題的n/2的特征，還有一種適應(yīng)于本題做法： 數(shù)組存在一個(gè)數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長(zhǎng)度的一半，也就是說它出現(xiàn)的次數(shù)比其他所有數(shù)字出現(xiàn)的次數(shù)和還多。因此，我們可以在遍歷數(shù)組的過程中維護(hù)兩個(gè)值：一個(gè)是數(shù)組的元素值，一個(gè)是次數(shù)。當(dāng)我們遍歷到下一個(gè)數(shù)字的時(shí)候，如果下一個(gè)數(shù)字和之前保存的數(shù)字相同，則次數(shù)加1；如果不同，則次數(shù)減1.如果次數(shù)為0，則保存下一個(gè)元素，并把次數(shù)設(shè)為1。由于我們要找的數(shù)字出現(xiàn)的次數(shù)比其他所有數(shù)字出現(xiàn)的次數(shù)之和還多，那么要找的數(shù)字肯定就是最后一次把次數(shù)設(shè)為1時(shí)對(duì)應(yīng)的數(shù)字，并且這種解法不需要改變數(shù)組本身，也不需要額外空間。

class Solution2{
public:
    int MoreThanHalfNum(vector<int> numbers){
        if (numbers.size() == 0)
            return 0;
        int result = numbers[0];
        int times = 1;
        for (int i = 1; i < numbers.size(); ++i){
            if (times == 0){
                result = numbers[i];
                times = 1;
            }
            else if (numbers[i] == result)
                times++;
            else
                times--;
        }
        return res;
    }
}

相似題目

本題與LeetCode中的169. Majority Element完全一致，可以在上面進(jìn)行代碼驗(yàn)證。
此題代碼可以參考：Leetcode 169 code
另外也可以在牛客網(wǎng) 劍指offer上進(jìn)行代碼驗(yàn)證。

面試題30： 最小的k個(gè)數(shù)

題目： 輸入n個(gè)整數(shù)，找出其中最小的k個(gè)數(shù)。例如，輸入4,5,1,6,2,7,3,8 這8個(gè)數(shù)字，則最小的4個(gè)數(shù)字是1,2,3,4。

題目分析

雖然這不是一道明確的數(shù)組問題，但是因?yàn)槠渑c29題同屬于top-k問題，所以也將其放在數(shù)組專題中。這里介紹top-k問題的堆排序解法，這種解法適合海量數(shù)據(jù)問題。

在最大堆中根結(jié)點(diǎn)的值總是大于它的子樹中任意節(jié)點(diǎn)的值。于是我們每次可以在O(1)得到已有的k個(gè)數(shù)字中的最大值。

參考代碼中給出了partation的做法，利用最大堆的做法，以及利用紅黑樹的做法。主要建議采用最大堆。

參考代碼

#include<iostream>
#include<vector>
#include<stdlib.h>
using namespace std;

/*==============常規(guī)數(shù)據(jù)===================*/
class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> result;
        if (k > input.size() || k <= 0)
            return result;

        int start = 0;
        int end = input.size() - 1;
        int index = Partation(input, start, end);
        while (index != k - 1){     //找到所在位置的數(shù)為止
            if (index > k - 1){
                end = index - 1;
                index = Partation(input, start, end);
            }
            if (index < k - 1){
                start = index + 1;
                index = Partation(input, start, end);
            }
        }

        for (int i = 0; i < k; ++i){
            result.push_back(input[i]);
        }
        return result;
    }

private:
    void Swap(int* i, int* j){
        int temp = *i;
        *i = *j;
        *j = temp;
    }

    int Random(int start, int end){
        if (end > start){
            return start + rand() % (end - start);
        }
        else
            return 0;
    }

    int Partation(vector<int>& data, int start, int end){       //因?yàn)橐淖僤ata所以采用引用
        int middle = Random(start, end);
        Swap(&data[middle], &data[end]);    //以end處作為基準(zhǔn)

        int small = start - 1;      //哨兵作用
        for (int i = start; i < end; ++i){
            if (data[i] < data[end]){
                ++small;
                if (small != i)     //防止多余交換
                    Swap(&data[small], &data[i]);
            }
        }

        ++small;
        Swap(&data[small], &data[end]);

        return small;
    }
};

/*==================海量數(shù)據(jù)采用最大堆================*/
/*
class Solution{
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k){
        int len = input.size();
        if (len <= 0 || k > len || k <= 0)
            return vector<int>();       //輸出空vector
        vector<int> res(input.begin(), input.begin() + k);  //結(jié)果中裝填前k個(gè)數(shù)
        //建立最大堆
        make_heap(res.begin(), res.end());
        for (int i = k; i < len; ++i){
            if (input[i] < res[0]){
                //先pop，然后再容器中刪除
                pop_heap(res.begin(), res.end());   //將最大元素pop并將剩余元素重新維護(hù)為一個(gè)堆
                res.pop_back();
                //先在容器中加入，再push
                res.push_back(input[i]);
                push_heap(res.begin(), res.end());     //對(duì)剛插入的元素做堆排序
            }
        }
        sort_heap(res.begin(), res.end());  //從小到大
        return res;
    }
};
*/

/*==================海量數(shù)據(jù)利用紅黑樹_multiset=================*/
/*
class Solution{
public:
    vector<int> GetleastNumbers_Solution(vector<int> input, int k){
        int len = input.size();
        if (len <= 0 || k > len || k <= 0)
            return vector<int>();
        //仿函數(shù)中的greater<T>模板，從大到小排序
        multiset<int, greater<int>> leastNums;
        vector<int>::iterator vec = input.begin();
        for (; vec != input.end(); ++vec){
            //將前k個(gè)元素插入集合
            if (leastNums.size() < k)
                leastNums.insert(*vec);
            else{
                //第一個(gè)元素是最大值
                //multiset<int, greater<int>>::iterator greatest = leastNums.begin();
                //如果后續(xù)元素小于最大值，刪除第一個(gè)，插入當(dāng)前元素
                if (*vec < *(leastNums.begin()){
                    leastNums.erase(leastNums.begin());
                    leastNums.insert(*vec);
                }
            }
        }
        return vector<int>(leastNums.begin(), leastNums.end());
    }
};
*/


int main()
{
    vector<int> input = {4,5,1,6,2,7,3,8};
    Solution solu;
    vector<int> output = solu.GetLeastNumbers_Solution(input, 4);

    for (int i = 0; i < 4; ++i){
        cout << output[i] << " ";
    }

    return 0;
}

相似題目

此題與LeetCode中的215. Kth Largest Element in an Array相似，LeetCode中是求最大的k個(gè)數(shù)，因此采用最小堆。
可以參考LeetCode 215 code
同樣也可以在牛客網(wǎng) 劍指offer中對(duì)代碼進(jìn)行驗(yàn)證。

面試題31： 連續(xù)子數(shù)組的最大和

題目：輸入一個(gè)整型數(shù)組，數(shù)組里有正數(shù)也有負(fù)數(shù)。數(shù)組中一個(gè)或連續(xù)的多個(gè)整數(shù)組成一個(gè)子數(shù)組。求所有子數(shù)組的和的最大值。要求時(shí)間復(fù)雜度為O(n)。
例如輸入的數(shù)組為{1,2,3,10,-4,7,2,-5},和最大的子數(shù)組為{3,10,-4,7,2},因此輸出的子數(shù)組和為18。

題目分析

這是一道簡(jiǎn)單的動(dòng)態(tài)規(guī)劃的題，只需維護(hù)一個(gè)局部變量和一個(gè)全局變量即可通過遍歷一遍數(shù)組完成題解。可以直接通過代碼理解。

參考代碼

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {

        int local_max = array[0];
        int global_max = array[0];
        for (int i = 1; i < array.size(); ++i){
            local_max = local_max + array[i];
            local_max = max(local_max, array[i]);
            global_max = max(local_max, global_max);
        }
        return global_max;
    }
};

相似題目

本題與LeetCode中的53. Maximum Subarray完全一致，另外LeetCode中還有一道子數(shù)組最大積的問題152. Maximum Product Subarray，同樣也可以利用本題中的思想完成。
下面是這兩道題的參考代碼：
LeetCode 53 code
LeetCode 152 code

除LeetCode外，也可以在?？途W(wǎng) 劍指offer上完成本題。

面試題33: 把數(shù)組排成最小的數(shù)

題目： 輸入一個(gè)正整數(shù)數(shù)組，把數(shù)組里所有數(shù)字拼接起來(lái)構(gòu)成一個(gè)數(shù)，打印能拼接處的所有數(shù)字中最小的一個(gè)。例如輸入數(shù)組{3,32,321}，則打印出這3個(gè)數(shù)字能排成的最小數(shù)字321323。

題目分析

這道題最直接的做法是先求出數(shù)組中所有數(shù)字的全排列，然后得出最小值。但是這樣n個(gè)數(shù)字會(huì)有n！個(gè)排列。效率會(huì)很差，我們應(yīng)該從排序規(guī)則入手，找到更高效的解題方法。
要確定一個(gè)排序規(guī)則，則要比較兩個(gè)數(shù)字，對(duì)于m和n有兩種排序方法mn、nm，我們需要判斷的是mn與nm的大小。而如何比較一個(gè)拼接數(shù)字的大小，最簡(jiǎn)單的方法就是將數(shù)字轉(zhuǎn)化為字符串。參考代碼如下。

參考代碼

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
class Solution {
public:
    static bool compare(int a, int b){  //傳入sort中的參數(shù)必須為static
        string A = "";
        string B = "";
        A += to_string(a);
        A += to_string(b);
        B += to_string(b);
        B += to_string(a);

        return A < B;   //這里的小于號(hào)是字符串的比較
    }
    string PrintMinNumber(vector<int> numbers) {
        string res = "";
        sort(numbers.begin(), numbers.end(), compare);
        for (int i = 0; i < numbers.size(); ++i){
            res += to_string(numbers[i]);
        }

        return res;
    }
};

int main()
{
    vector<int> nums = {3,32,321};
    Solution solu;
    cout << solu.PrintMinNumber(nums) << endl;

    return 0;
}

相似題目

本題與LeetCode中的179. Largest Number題類似，只是LeetCode中要求的是排列成最大的數(shù)。
此題的參考代碼可見：
LeetCode 179 code

可以在?？途W(wǎng) 劍指offer中驗(yàn)證代碼的正確性。

面試題36： 數(shù)組中的逆序?qū)?/h3>

題目： 在數(shù)組中的兩個(gè)數(shù)字如果前面一個(gè)數(shù)字大于后面的數(shù)字，則這兩個(gè)數(shù)組組成一個(gè)逆序?qū)?。輸入一個(gè)數(shù)組，求出這個(gè)數(shù)組中的逆序?qū)Φ目倲?shù)。
例如，在數(shù)組{7,5,6,4}中，一共存在5個(gè)逆序?qū)?，分別是(7,6),(7,5),(7,4),(6,4),(5,4)。

題目分析

以數(shù)組{7,5,6,4}為例分析統(tǒng)計(jì)逆序?qū)Φ倪^程。我們考慮先比較相鄰的數(shù)字。
如圖1與圖2所示，先把數(shù)組分解為兩個(gè)長(zhǎng)度為2的子數(shù)組，再把這兩個(gè)子數(shù)組分別拆分成兩個(gè)長(zhǎng)度為1的子數(shù)組。接下來(lái)一邊合并相鄰的子數(shù)組，一邊統(tǒng)計(jì)逆序?qū)Φ臄?shù)目。

圖1

圖2

對(duì)算法熟悉的人可以發(fā)現(xiàn)圖1和圖2所描述的過程正是歸并排序。先把數(shù)組分割成子數(shù)組，先統(tǒng)計(jì)出子數(shù)組內(nèi)部的逆序?qū)?shù)目，然后再統(tǒng)計(jì)出兩個(gè)相鄰子數(shù)組之間的逆序?qū)?shù)目。在統(tǒng)計(jì)逆序?qū)Φ倪^程中，還需要對(duì)數(shù)組進(jìn)行排序。同理，冒泡排序也能完成本題，但是冒泡排序其實(shí)就是本題的暴力方法。

參考代碼

#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    int InversePairs(vector<int> data) {
        int length = data.size();
        if (length <= 0)
            return 0;
        vector<int> copy(length);

        int count = InversePairsCore(data, copy, 0 ,length - 1);
        return count;
    }
private:
    int InversePairsCore(vector<int> &data, vector<int> &copy, int start, int end){
        if (start == end){      //遞歸結(jié)束條件,當(dāng)只有一個(gè)數(shù)時(shí)返回
            copy[start] = data[start];      //將最后數(shù)據(jù)存入copy中
            return 0;
        }

        int length = (end - start) / 2;

        int left = InversePairsCore(data, copy, start, start + length);
        int right = InversePairsCore(data, copy, start + length + 1, end);

        //i初始化為前半段最后一個(gè)
        int i = start + length;
        //j初始化為后半段最后一個(gè)
        int j = end;
        int indexCopy = end;
        int count = 0;
        while (i >= start && j >= start + length + 1){
            if (data[i] > data[j]){
                copy[indexCopy] = data[i];
                indexCopy--;
                i--;
                count += (j - start - length);
            }
            else{
                copy[indexCopy] = data[j];
                indexCopy--;
                j--;
            }
        }

        for (; i >= start; --i){
            copy[indexCopy] = data[i];
            indexCopy--;

        }
        for (; j >= start + length + 1; --j){
            copy[indexCopy] = data[j];
            indexCopy--;
        }

        for (int i = start; i <= end; ++i){     //保證data有序
            data[i] = copy[i];
        }
        return count + left + right;

    }
};

int main()
{
    vector<int> data = {7,5,6,4};
    Solution solu;
    cout << solu.InversePairs(data) << endl;

    return 0;
}

相似題目

可以在?？途W(wǎng) 劍指offer上完成本題。

面試題38： 數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)

題目： 統(tǒng)計(jì)一個(gè)數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)。例如輸入排序數(shù)組{1,2,3,3,3,3,4,5}和數(shù)字3，由于3在這個(gè)數(shù)組中出現(xiàn)了4次，因此輸出4。

題目分析

本題是一個(gè)統(tǒng)計(jì)次數(shù)的問題，可以直接一遍便利即可得出結(jié)果，這樣的時(shí)間復(fù)雜度為O(n)。但是這樣沒有利用到數(shù)組的排序特性。這里可以使用兩次二分查找，以題目中的例子說明，只要找到第一個(gè)3與最后一個(gè)3的位置，即可得出題解。

參考代碼

#include<iostream>
#include<vector>

using namespace std;

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        if (data.size() <= 0)
            return 0;
        int FirstK = GetFirstK(data, k, 0, data.size() - 1);
        int LastK = GetLastK(data, k, 0, data.size() - 1);

        if (LastK != -1 && FirstK != -1)
            return LastK - FirstK + 1;
        else
            return 0;

    }
private:
    int GetFirstK(vector<int> data, int k, int start, int end){
        if (start > end)    //遞歸結(jié)束條件
            return -1;
        int middle = start + (end - start) / 2;
        if (data[middle] == k){
            if ((middle > 0 && data[middle - 1] != k) || middle == 0)
                return middle;
            else
                end = middle - 1;
        }
        else if (data[middle] > k){
            end = middle - 1;
        }
        else if (data[middle] < k){
            start = middle + 1;
        }
        return GetFirstK(data, k, start, end);
    }

    int GetLastK(vector<int> data, int k, int start, int end){
        if (start > end)    //遞歸結(jié)束條件
            return -1;
        int middle = start + (end - start) / 2;
        if (data[middle] == k){
            if ((middle < end && data[middle + 1] != k) || middle == end)
                return middle;
            else
                start = middle + 1;
        }
        else if (data[middle] > k){
            end = middle - 1;
        }
        else if (data[middle] < k){
            start = middle + 1;
        }
        return GetLastK(data, k, start, end);
    }
};

int main()
{
    Solution solu;
    vector<int> data = {1,3,3,3,3,4,5};
    cout << solu.GetNumberOfK(data,2) << endl;

    return 0;
}

相似題目

可以在?？途W(wǎng) 劍指offer中完成對(duì)本題的練習(xí)。

面試題40： 數(shù)組中只出現(xiàn)一次的數(shù)字

題目： 一個(gè)整型數(shù)組里除了兩個(gè)數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次。請(qǐng)寫程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字。要求時(shí)間復(fù)雜度為O(n),空間復(fù)雜度為O(1)。

題目分析

看到此題最直接的想法就是構(gòu)建一個(gè)hash table，但是這樣的空間復(fù)雜度不符合題目要求。所以要根據(jù)題目中的除了兩個(gè)數(shù)字之外其他的都出現(xiàn)了兩次來(lái)找到更高效的解法。

我們先假設(shè)數(shù)組中只有一個(gè)數(shù)字出現(xiàn)了一次，其他數(shù)字都出現(xiàn)了兩次。根據(jù)異或運(yùn)算的性質(zhì)：任何一個(gè)數(shù)字異或它自己都等于0.也就是說，如果我們從頭到尾依次異或數(shù)組中的每一個(gè)數(shù)字，那么最終得到的就是那個(gè)只出現(xiàn)一次的數(shù)字。

回到原始題目，看看能否采用相同的思想。如果我們能夠?qū)⒃瓟?shù)組分成兩個(gè)數(shù)組，而兩個(gè)數(shù)字正好分別在這兩個(gè)數(shù)組中就好了。

首先，我們從頭到尾依次異或數(shù)組中的每一個(gè)數(shù)字，最終的到的是兩個(gè)目標(biāo)數(shù)字的異或結(jié)果。我們可以根據(jù)這個(gè)結(jié)果對(duì)數(shù)組進(jìn)行分組。

由于這兩個(gè)數(shù)字肯定是不一樣的，所以最終的異或結(jié)果肯定不為0，也就是說這個(gè)結(jié)果中至少有一位為1（二進(jìn)制）。將第一個(gè)1的位置即為n，則根據(jù)第n位是否為1給數(shù)組分組，則相同數(shù)組肯定會(huì)被分到一組，而n位是由兩個(gè)目標(biāo)數(shù)字異或得到的，所以必定在此為上一個(gè)為0一個(gè)為1。所以可以正確的將數(shù)組分為兩組，并且兩個(gè)目標(biāo)數(shù)字分別處于兩組中。

可以以《劍指offer》中{2,4,3,6,3,2,5,5}為例進(jìn)行上面的步驟理解。

參考代碼

#include<iostream>
#include<vector>

using namespace std;

/*=============利用vector構(gòu)建hash==================*/
class Solution
{
public:
    vector<int> FindNumsAppearOnce(vector<int> data)
    {
        vector<int> result;
        vector<int> hashtable(data.size(), 0);
        for (int i = 0; i < data.size(); ++i)
        {
            hashtable[data[i]]++;
        }
        for (int i = 0; i < hashtable.size(); ++i)
        {
            if (hashtable[data[i]] == 1)
               result.push_back(data[i]);
        }
        return result;
    }
};

/*================時(shí)間復(fù)雜度為O(n),空間復(fù)雜度為O(1)的方法=================*/
class Solution2
{
public:
    void FindNumsAppearOnce(vector<int> data, int* num1, int* num2)
    {
        if (data.size() <= 0)
            return;
        int result_temp = 0;
        for (int i = 0; i < data.size(); ++i)
        {
            result_temp = result_temp ^ data[i];
        }
        int TheFirst1 = FindFirst1(result_temp);
        *num1 = *num2 = 0;
        for (int i = 0; i < data.size(); ++i)
        {
            if (Is1(data[i], TheFirst1))
                *num1 = *num1 ^ data[i];
            else
                *num2 = *num2 ^ data[i];
        }
    }
private:
    int FindFirst1(int num)
    {
        int index = 0;
        while (((num & 1) == 0) && index < 8*sizeof(int))
        {
            num = num >> 1;
            index++;
        }
        return index;
    }

    bool Is1(int num, int index)
    {
        num = num >> index;
        return (num & 1);
    }

};

int main()
{
    Solution solu;
    vector<int> result;
    vector<int> data = {2,4,3,6,3,2,5,5};
    result = solu.FindNumsAppearOnce(data);

    for (int i = 0; i < result.size(); ++i)
    {
        cout << result[i] << " ";
    }

    return 0;
}

相似題目

本題與LeetCode中的260. Single Number III完全一致，另外，LeetCode中還有一道此題的簡(jiǎn)化版本，即找到唯一的一個(gè)出現(xiàn)次數(shù)為1的數(shù)字136. Single Number;
LeetCode中還有一道此題的擴(kuò)展版本，除了一個(gè)數(shù)字出現(xiàn)1次其他出現(xiàn)3次，要求找出這個(gè)唯一的數(shù)字137. Single Number II
這三道題的參考代碼見：
LeetCode 260 code
LeetCode 136 code
LeetCode 137 code

還可以在?？途W(wǎng) 劍指offer中完成對(duì)本題的練習(xí)。

面試題51: 數(shù)組中重復(fù)的數(shù)字

題目： 在一個(gè)長(zhǎng)度為n的數(shù)組中的所有數(shù)字都在0~n-1之間。數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個(gè)數(shù)字重復(fù)了，也不知道每個(gè)數(shù)字重復(fù)了幾次。請(qǐng)找出數(shù)組中第一個(gè)重復(fù)的數(shù)字。

題目分析

看到此題最直接的想法是將數(shù)組排序，在排序數(shù)組中找到重復(fù)元素是很容易的一件事。
當(dāng)然還可以利用hash的方法來(lái)解決這個(gè)問題。

但是都沒有充分利用到0~n-1這個(gè)條件，下面我們看有沒有更高效的方法。

由于數(shù)組中的元素都在0~n-1的范圍內(nèi)，如果這個(gè)數(shù)組中沒有重復(fù)的數(shù)字，那么當(dāng)數(shù)組排序之后數(shù)字i將出現(xiàn)在下標(biāo)為i的位置。由于數(shù)組中存在重復(fù)的數(shù)字，則有些位置可能存在多個(gè)數(shù)字，有些位置可能沒有數(shù)組。根據(jù)這個(gè)特點(diǎn)我們得到下面的解法。

從頭到尾依次掃描數(shù)組中的每個(gè)數(shù)字。當(dāng)掃描到下標(biāo)為i的數(shù)字時(shí)，首先比較這個(gè)數(shù)字（用m表示）是否等于i。如果是，接著掃描下一個(gè)數(shù)字。如果不是，則那它與第m個(gè)數(shù)字進(jìn)行比較。如果它和m個(gè)數(shù)字相等，就找到了第一個(gè)重復(fù)數(shù)字，如果不等，則把第i個(gè)數(shù)字與第m個(gè)數(shù)字交換位置，讓m回到屬于它的下標(biāo)位置去。接下來(lái)重復(fù)這個(gè)比較，交換的過程，即可找出所有重復(fù)數(shù)字。

可以以書中給出的{2,3,1,0,2,5,3}數(shù)組為例進(jìn)行上面的分析理解。

參考代碼

#include<iostream>
#include<vector>

using namespace std;

class Solution {
public:
    //暴力解法
    bool duplicate(vector<int> numbers, int length, int* duplication) {
        if (length <= 0)
            return false;

        bool found = false;
        for (int i = 0; i < length; ++i){
            for (int j = i + 1; j < length; ++j){
                if (numbers[i] == numbers[j]){
                    *duplication = numbers[i];
                    found = true;
                    break;
                }
                if (found == true)
                    break;
            }
        }
        return found;
    }

    //答案解法
        bool duplicate2(vector<int> numbers, int length, int* duplication) {
        if (length <= 0)
            return false;
        for (int i = 0; i < length; ++i){
            if (numbers[i] > length -1 || numbers[i] < 0)
                return false;
        }

        for (int i = 0; i < length; ++i){
            while (numbers[i] != i){
                if (numbers[i] == numbers[numbers[i]]){
                    *duplication = numbers[i];
                    return true;
                }
                Swap(&numbers[i],&numbers[numbers[i]]);
            }
        }
        return false;
    }
    //還可以利用hash，先排序等解法。
private:
    void Swap (int* i, int* j)
    {
        int temp = *i;
        *i = *j;
        *j = temp;
    }

};

int main()
{
    vector<int> numbers = {2,3,1,0,2,5,3};
    Solution solu;
    int duplication1 = 0;
    int duplication2 = 0;

    bool result1 = solu.duplicate(numbers, numbers.size(), &duplication1);
    bool result2 = solu.duplicate2(numbers, numbers.size(), &duplication2);

    cout << result1 << " " << duplication1 << endl;
    cout << result2 << " " << duplication2 << endl;

    return 0;

}

相似題目

此題與LeetCode中的287. Find the Duplicate Number完全一致。此題的參考代碼見：
LeetCode 287 code
還可以在?？途W(wǎng) 劍指offer上完成對(duì)本題的練習(xí)。

面試題52： 構(gòu)建乘積數(shù)組

題目： 給定一個(gè)數(shù)組A[0,1,...,n-1],請(qǐng)構(gòu)建一個(gè)數(shù)組B[0,1,...,n-1],其中B中的元素B[i]=A[0]×A[1]×...×A[i-1]×A[i+1]×...×A[n-1]。不能使用除法。

題目分析

本題要求不能使用除法，直觀的解法是直接連乘n-1個(gè)數(shù)字得到B[i]，但是顯然這種做法并不是我們想得到的結(jié)果。

此題更高效的方法是將B[i]=A[0]×A[1]×...×A[i-1]×A[i+1]×...×A[n-1]分為兩部分解決，從i處分割為A[0]×A[1]×...×A[i-1]與A[i+1]×...×A[n-1]。

不妨設(shè)C[i]=A[0]×A[1]×...×A[i-1]；D[i]=A[i+1]×...×A[n-1]，則C[i]=C[i-1]×A[i-1]; D[i]=D[i+1]×A[i+1];

參考代碼

#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    //將數(shù)組分為兩部分
    vector<int> multiply1(const vector<int>& A) {
        int length = A.size();
        vector<int> result(length);
        if (length <= 0)
            return result;

        //賦值前半部分
        result[0] = 1;
        for (int i = 1; i < length; ++i){
            result[i] = result[i - 1] * A[i - 1];
        }

        //賦值后半部分
        int temp = 1;
        for (int i = length - 1; i >= 0; --i){
            result[i] = result[i] * temp;
            temp = temp * A[i];
        }
        return result;
    }

    //同樣是分為兩組，可讀性更好的代碼
    vector<int> multiply(const vector<int>& A) {
        int count = A.size();
        vector<int> res(count, 1);
        vector<int> left(count, 1);
        vector<int> right(count, 1);

        for (int i = 1; i < count; ++i){
            left[i] = left[i-1] * A[i-1];
        }
        for (int i = count - 2; i >= 0; --i){
            right[i] = right[i+1] * A[i+1];
        }

        for (int i = 0; i < count; ++i){
            res[i] = left[i] * right[i];
        }
        return res;
    }
};

int main()
{
    vector<int> A = {1,2,3,4,5};
    vector<int> result;
    Solution solu;
    result = solu.multiply(A);

    for (int i = 0; i < result.size(); ++i)
    {
        cout << result[i] << " " << endl;
    }

    return 0;
}

相似題目

本題與LeetCode中的238. Product of Array Except Self完全一致，代碼見：
LeetCode 238 code
同樣還可以在?？途W(wǎng) 劍指offer上完成對(duì)本題的練習(xí)。

【參考】
[1]《劍指offer》

歡迎轉(zhuǎn)載，轉(zhuǎn)載請(qǐng)注明出處：wenmingxing 《劍指offer》數(shù)組專題