數(shù)組

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

相關(guān)題目列表

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

題目

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

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

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

題目分析

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

矩陣示例

首先選取數(shù)組中右上角的數(shù)字<9>。如果該數(shù)字等于要查找的數(shù)字抹竹，查找過程結(jié)束线罕；如果該數(shù)字大于要查找的數(shù)字，剔除這個數(shù)字所在的列<9,12,13,15>（因為這一列必定都大于所要查找的數(shù)字）柒莉；如果該數(shù)字小于要查找的數(shù)字闻坚，剔除這個數(shù)字所在的行（因為這一行必定都大于要查找的數(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;       //所在列遞減表明向左移動
            else
                ++row;  //所在行遞增窗轩，表明逐漸向下移動
        }
    }
    return result;
}

//=====================測試樣例=====================

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;
}

上面的代碼是通過指針來表示一個二維數(shù)組的夯秃，也可以通過vector<vector<int>> 來表示一個數(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ǎng) 劍指offer上完成本題哺呜。

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

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

題目分析

這道題最直觀的做法就是直接遍歷數(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ù)組本身有序，直接返回第一個元素谆构，即是最小元素

    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;

        //如果三個指針位置數(shù)值大小相等，則無法確定中間位置屬于遞增部分還是遞減部分框都，只能采用遍歷方式
        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()    //一般測試樣例
{
    int numbers[] = {3,4,5,1,2};
    cout << Min(numbers, 5) << endl;
}

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

void test3()    //測試樣例3，測試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>的方式谓罗。
因為代碼中都帶有詳細(xì)的注釋粱哼，所以如果不是特別復(fù)雜的邏輯結(jié)構(gòu)，都直接以代碼的形式展示題解檩咱。Just Show Me Your Code揭措！

相似題目

本題與LeetCode中的153. Find Minimum in Rotated Sorted Array完全一致】舔牵可以在上面進(jì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ù)之前

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

題目分析

數(shù)組示例

對于這道題，很容易想到的方法是維護(hù)兩個指針left伴找，right妙蔗，分別指向數(shù)組的首尾位置，采用雙向遍歷的方式疆瑰，如果left指向的元素為偶數(shù)眉反，且right指向的元素為奇數(shù)，則交換兩個元素穆役。直到遍歷玩整個數(shù)組寸五，即可滿足條件。參考代碼如1耿币。

值得注意的是梳杏，對于這道題，存在擴(kuò)展性的解法淹接，因為題目要求是區(qū)分奇偶數(shù)十性，這只是這類問題的一個特例，我們也可以通過傳入函數(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ǎng) 劍指offer上完成對本題的驗證霞势。

面試題20： 順時針打印矩陣

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

矩陣示例

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

題目分析

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

參考代碼

#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)行驗證。
此題參考代碼見：
LeetCode 54 code ??? 這里與參考代碼是不同的，以方便選擇自己認(rèn)為可讀性更好的代碼進(jìn)行閱讀。
還可以在叛堕牛客網(wǎng) 劍指offer上對編碼進(jìn)行驗證寞焙。

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

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

題目分析

本題最容易想到的方法就是排序去扣，排序數(shù)組的中間位置即為所求柱衔。
接下來思考是否還有效率更高的方法。由題目可知，該題就是找到數(shù)組中的中位數(shù)唆铐。即長度為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題中會介紹王浴。

另外根據(jù)本題的n/2的特征脆炎，還有一種適應(yīng)于本題做法： 數(shù)組存在一個數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半，也就是說它出現(xiàn)的次數(shù)比其他所有數(shù)字出現(xiàn)的次數(shù)和還多氓辣。因此秒裕，我們可以在遍歷數(shù)組的過程中維護(hù)兩個值：一個是數(shù)組的元素值，一個是次數(shù)筛婉。當(dāng)我們遍歷到下一個數(shù)字的時候簇爆，如果下一個數(shù)字和之前保存的數(shù)字相同，則次數(shù)加1爽撒；如果不同入蛆，則次數(shù)減1.如果次數(shù)為0，則保存下一個元素硕勿，并把次數(shù)設(shè)為1哨毁。由于我們要找的數(shù)字出現(xiàn)的次數(shù)比其他所有數(shù)字出現(xiàn)的次數(shù)之和還多，那么要找的數(shù)字肯定就是最后一次把次數(shù)設(shè)為1時對應(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)行代碼驗證话浇。
此題代碼可以參考：Leetcode 169 code
另外也可以在牛客網(wǎng) 劍指offer上進(jìn)行代碼驗證闹究。

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

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

題目分析

雖然這不是一道明確的數(shù)組問題价认，但是因為其與29題同屬于top-k問題嗅定，所以也將其放在數(shù)組專題中。這里介紹top-k問題的堆排序解法用踩，這種解法適合海量數(shù)據(jù)問題渠退。

在最大堆中根結(jié)點(diǎn)的值總是大于它的子樹中任意節(jié)點(diǎn)的值忙迁。于是我們每次可以在O(1)得到已有的k個數(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){       //因為要改變data所以采用引用
        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個數(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ù)為一個堆
                res.pop_back();
                //先在容器中加入，再push
                res.push_back(input[i]);
                push_heap(res.begin(), res.end());     //對剛插入的元素做堆排序
            }
        }
        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個元素插入集合
            if (leastNums.size() < k)
                leastNums.insert(*vec);
            else{
                //第一個元素是最大值
                //multiset<int, greater<int>>::iterator greatest = leastNums.begin();
                //如果后續(xù)元素小于最大值删豺，刪除第一個，插入當(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個數(shù)呀页，因此采用最小堆。
可以參考LeetCode 215 code
同樣也可以在庞堤常客網(wǎng) 劍指offer中對代碼進(jìn)行驗證蓬蝶。

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

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

題目分析

這是一道簡單的動態(tài)規(guī)劃的題，只需維護(hù)一個局部變量和一個全局變量即可通過遍歷一遍數(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ǎng) 劍指offer上完成本題。

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

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

題目分析

這道題最直接的做法是先求出數(shù)組中所有數(shù)字的全排列羔巢，然后得出最小值望忆。但是這樣n個數(shù)字會有n罩阵！個排列。效率會很差启摄，我們應(yīng)該從排序規(guī)則入手稿壁，找到更高效的解題方法。
要確定一個排序規(guī)則歉备，則要比較兩個數(shù)字傅是，對于m和n有兩種排序方法mn、nm蕾羊，我們需要判斷的是mn與nm的大小喧笔。而如何比較一個拼接數(shù)字的大小，最簡單的方法就是將數(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;   //這里的小于號是字符串的比較
    }
    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ǎng) 劍指offer中驗證代碼的正確性。

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

題目： 在數(shù)組中的兩個數(shù)字如果前面一個數(shù)字大于后面的數(shù)字哀澈，則這兩個數(shù)組組成一個逆序?qū)ε平琛］斎胍粋€數(shù)組，求出這個數(shù)組中的逆序?qū)Φ目倲?shù)日丹。
例如走哺，在數(shù)組{7,5,6,4}中，一共存在5個逆序?qū)φ芟海謩e是(7,6),(7,5),(7,4),(6,4),(5,4)丙躏。

題目分析

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

圖1

圖2

對算法熟悉的人可以發(fā)現(xiàn)圖1和圖2所描述的過程正是歸并排序扒寄。先把數(shù)組分割成子數(shù)組鱼鼓，先統(tǒng)計出子數(shù)組內(nèi)部的逆序?qū)?shù)目，然后再統(tǒng)計出兩個相鄰子數(shù)組之間的逆序?qū)?shù)目该编。在統(tǒng)計逆序?qū)Φ倪^程中迄本，還需要對數(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)只有一個數(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初始化為前半段最后一個
        int i = start + length;
        //j初始化為后半段最后一個
        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ǎng) 劍指offer上完成本題公条。

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

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

題目分析

本題是一個統(tǒng)計次數(shù)的問題，可以直接一遍便利即可得出結(jié)果抓韩，這樣的時間復(fù)雜度為O(n)纠永。但是這樣沒有利用到數(shù)組的排序特性。這里可以使用兩次二分查找谒拴，以題目中的例子說明尝江，只要找到第一個3與最后一個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ǎng) 劍指offer中完成對本題的練習(xí)。

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

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

題目分析

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

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

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

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

由于這兩個數(shù)字肯定是不一樣的，所以最終的異或結(jié)果肯定不為0，也就是說這個結(jié)果中至少有一位為1（二進(jìn)制）送火。將第一個1的位置即為n，則根據(jù)第n位是否為1給數(shù)組分組先匪，則相同數(shù)組肯定會被分到一組种吸，而n位是由兩個目標(biāo)數(shù)字異或得到的，所以必定在此為上一個為0一個為1呀非。所以可以正確的將數(shù)組分為兩組坚俗，并且兩個目標(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;
    }
};

/*================時間復(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中還有一道此題的簡化版本降允，即找到唯一的一個出現(xiàn)次數(shù)為1的數(shù)字136. Single Number;
LeetCode中還有一道此題的擴(kuò)展版本恩闻，除了一個數(shù)字出現(xiàn)1次其他出現(xiàn)3次，要求找出這個唯一的數(shù)字137. Single Number II
這三道題的參考代碼見：
LeetCode 260 code
LeetCode 136 code
LeetCode 137 code

還可以在啪缍客網(wǎng) 劍指offer中完成對本題的練習(xí)幢尚。

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

題目： 在一個長度為n的數(shù)組中的所有數(shù)字都在0~n-1之間。數(shù)組中某些數(shù)字是重復(fù)的翅楼，但不知道有幾個數(shù)字重復(fù)了尉剩，也不知道每個數(shù)字重復(fù)了幾次。請找出數(shù)組中第一個重復(fù)的數(shù)字毅臊。

題目分析

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

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

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

從頭到尾依次掃描數(shù)組中的每個數(shù)字美浦。當(dāng)掃描到下標(biāo)為i的數(shù)字時，首先比較這個數(shù)字（用m表示）是否等于i项栏。如果是浦辨，接著掃描下一個數(shù)字。如果不是沼沈，則那它與第m個數(shù)字進(jìn)行比較流酬。如果它和m個數(shù)字相等币厕，就找到了第一個重復(fù)數(shù)字，如果不等芽腾，則把第i個數(shù)字與第m個數(shù)字交換位置旦装，讓m回到屬于它的下標(biāo)位置去。接下來重復(fù)這個比較摊滔，交換的過程阴绢，即可找出所有重復(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ǎng) 劍指offer上完成對本題的練習(xí)。

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

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

題目分析

本題要求不能使用除法，直觀的解法是直接連乘n-1個數(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ǎng) 劍指offer上完成對本題的練習(xí)强岸。

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

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