1.leetcode-35. 搜索插入位置（簡(jiǎn)單）

（1）題目描述
給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值，在數(shù)組中找到目標(biāo)值，并返回其索引。如果目標(biāo)值不存在于數(shù)組中，返回它將會(huì)被按順序插入的位置。
請(qǐng)必須使用時(shí)間復(fù)雜度為 O(log n) 的算法。

（2）方法及思路（二分查找）
考慮這個(gè)插入的位置 pos，它成立的條件為：
nums[pos?1]<target≤nums[pos] ；
問(wèn)題轉(zhuǎn)化到這里，直接套用二分法即可，即不斷用二分法逼近查找第一個(gè)大于等于 target的下標(biāo) 。
（3）代碼實(shí)現(xiàn)

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        int l=0,r=n-1;
        while(l<=r){
            int mid=l+(r-l)/2;
            if(nums[mid]<target)
                l=mid+1;
            else r=mid-1;
        }
        return l;
    }
};

2.leetcode-74. 搜索二維矩陣（中等）

（1）題目描述
給你一個(gè)滿足下述兩條屬性的 m x n 整數(shù)矩陣：
每行中的整數(shù)從左到右按非遞減順序排列。
每行的第一個(gè)整數(shù)大于前一行的最后一個(gè)整數(shù)。
給你一個(gè)整數(shù) target ，如果 target 在矩陣中，返回 true ；否則，返回 false 。

（2）思路與方法（二分查找）
1.首先先把此二維數(shù)組看作是一個(gè)一維數(shù)組的變形。
2.若將矩陣每一行拼接在上一行的末尾，則會(huì)得到一個(gè)升序數(shù)組，我們可以在該數(shù)組上二分找到目標(biāo)元素。
3.代碼實(shí)現(xiàn)時(shí)，可以二分升序數(shù)組的下標(biāo)，將其映射到原矩陣的行和列上。
（3）代碼實(shí)現(xiàn)

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int low = 0, high = m * n - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            int x = matrix[mid/n][mid%n];
            if (x < target) {
                low = mid + 1;
            } else if (x > target) {
                high = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }
};

（特別要注意二分后mid的下標(biāo)）

3.leetcode-73. 矩陣置零（中等）

（1）題目描述
給定一個(gè) m x n 的矩陣，如果一個(gè)元素為 0 ，則將其所在行和列的所有元素都設(shè)為 0 。請(qǐng)使用 原地 算法。

（2）方法及思路（使用標(biāo)記數(shù)組）
1.先定義兩個(gè)一維數(shù)組，分別代表行和列
2.遍歷一遍數(shù)組，找出0元素所在的行和列，并在已定義的數(shù)組中用true賦值標(biāo)記出來(lái)。
3.再次遍歷數(shù)組，當(dāng)遍歷到被標(biāo)記的行或列時(shí)，就將其值改為0。
（3）代碼實(shí)現(xiàn)

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m=matrix.size();
        int n=matrix[0].size();
        vector<int> row(m),col(n);
        for(int i=0;i<m;++i)
        {
            for(int j=0;j<n;++j)
            {
                if(!matrix[i][j])
                {
                    row[i]=col[j]=true;
                }
            }
        }
        for(int i=0;i<m;++i)
        {
            for(int j=0;j<n;++j)
            {
                if(row[i]||col[j])
                {
                    matrix[i][j]=0;
                }
            }
        }
    } 
};

4.leetcode-56. 合并區(qū)間（中等）

（1）題目描述
以數(shù)組 intervals 表示若干個(gè)區(qū)間的集合，其中單個(gè)區(qū)間為 intervals[i] = [starti, endi] 。請(qǐng)你合并所有重疊的區(qū)間，并返回 一個(gè)不重疊的區(qū)間數(shù)組，該數(shù)組需恰好覆蓋輸入中的所有區(qū)間 。

（2）方法及思路（排序）
思路：
如果我們按照區(qū)間的左端點(diǎn)排序，那么在排完序的列表中，可以合并的區(qū)間一定是連續(xù)的。如下圖所示，標(biāo)記為藍(lán)色、黃色和綠色的區(qū)間分別可以合并成一個(gè)大區(qū)間，它們?cè)谂磐晷虻牧斜碇惺沁B續(xù)的：

算法：
1.我們用數(shù)組 merged 存儲(chǔ)最終的答案。
2.首先，我們將列表中的區(qū)間按照左端點(diǎn)升序排序。然后我們將第一個(gè)區(qū)間加入 merged 數(shù)組中，并按順序依次考慮之后的每個(gè)區(qū)間：
3.如果當(dāng)前區(qū)間的左端點(diǎn)在數(shù)組 merged 中最后一個(gè)區(qū)間的右端點(diǎn)之后，那么它們不會(huì)重合，我們可以直接將這個(gè)區(qū)間加入數(shù)組 merged 的末尾；
4.否則，它們重合，我們需要用當(dāng)前區(qū)間的右端點(diǎn)更新數(shù)組 merged 中最后一個(gè)區(qū)間的右端點(diǎn)，將其置為二者的較大值。

（3）代碼實(shí)現(xiàn)

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if(intervals.size()==0)
        {
            return {};
        }
        vector<vector<int>> merged;
        sort(intervals.begin(),intervals.end());
        for(int i=0;i<intervals.size();++i)
        {
            int left=intervals[i][0];
            int right=intervals[i][1];
            if(!merged.size()||merged.back()[1]<left)
            {
                merged.push_back({left,right});
            }
            else
            {
                merged.back()[1]=max(merged.back()[1],right);
            }
        }
        return merged;
    }
};

5.leetcode-54. 螺旋矩陣（中等）

給你一個(gè) m 行 n 列的矩陣 matrix ，請(qǐng)按照 順時(shí)針螺旋順序 ，返回矩陣中的所有元素。

（2）方法及思路（模擬）
可以模仿上一篇文章中的螺旋尋找
函數(shù)接受一個(gè)二維數(shù)組matrix作為參數(shù)，并返回一個(gè)一維數(shù)組ans。函數(shù)首先獲取二維數(shù)組的行數(shù)和列數(shù)，然后使用top、bottom、left和right來(lái)表示當(dāng)前螺旋循環(huán)的邊界。count表示剩余要輸出的元素個(gè)數(shù)。
在循環(huán)中，首先從左到右輸出上邊界的元素，每輸出一個(gè)元素，count減1并將其添加到ans中。然后將top加1，表示上邊界收縮。接下來(lái)從上到下輸出右邊界的元素，并更新右邊界。之后從右到左輸出下邊界的元素，更新下邊界。最后從下到上輸出左邊界的元素，更新左邊界。每次循環(huán)結(jié)束時(shí)，檢查count是否大于等于1，如果是則繼續(xù)循環(huán)，否則退出循環(huán)。
最后返回ans。
（3）代碼實(shí)現(xiàn)

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> ans;
        int m=matrix.size();
        int n=matrix[0].size();
        int top=0;
        int bottom=m-1;
        int left=0;
        int right=n-1;
        int count=m*n;
        while(count>=1)
        {
            for(int i=left;i<=right&&count>=1;++i) {ans.push_back(matrix[top][i]);count--;}
        top++;
        for(int i=top;i<=bottom&&count>=1;++i){ ans.push_back(matrix[i][right]);count--;}
        right--;
        for(int i=right;i>=left&&count>=1;--i) {ans.push_back(matrix[bottom][i]);count--;}
        --bottom;
        for(int i=bottom;i>=top&&count>=1;--i) {ans.push_back(matrix[i][left]);count--;}
        left++;
        }
        return ans;
    }
};

6.leetcode-1. 兩數(shù)之和（簡(jiǎn)單）

（1）題目描述
給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù)目標(biāo)值 target，請(qǐng)你在該數(shù)組中找出 和為目標(biāo)值 target 的那 兩個(gè) 整數(shù)，并返回它們的數(shù)組下標(biāo)。
你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案。但是，數(shù)組中同一個(gè)元素在答案里不能重復(fù)出現(xiàn)。
你可以按任意順序返回答案。

（2）方法及思路（雙指針）
先在頭上定義一個(gè)指針，在其后面也定義一個(gè)指針，然后循環(huán)找出符合要求的數(shù)。
（3）代碼實(shí)現(xiàn)文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-686571.html

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        vector<int> result;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] + nums[j] == target) {
                    vector<int> result;
                    result.push_back(i);
                    result.push_back(j);
                     return result;
                }
            }
        }
        return result;
    }
};

到了這里，關(guān)于【算法刷題之?dāng)?shù)組篇（2）】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！