🎇数组中等题Part

🌈 开启LeetCode刷题之旅 🌈

🍰229.多数元素II

多数元素II

👑思路分析

1.哈希表法

算法实现

建立一个哈希表 unordered_map<int,int> hash，其键值对表示数组内的元素及其出现的频次，当出现次数超过 $\lfloor \frac{n}{3}\rfloor$ ，则将该元素放入结果 $res$ 中，此时，时间复杂度和空间复杂度均为 $：O(n)$

在时间复杂度为 $O(n^2)$ 的算法中，对于一个符合条件的元素，我们可能会出现多次放入 $res$ 中的情况：

$Hash$表判断元素在数组中的方法：

注意：对于容器 $vector$ 而言，是没有判断元素存在的函数的，他们属于$STL$函数，所以需要调用头文件 #include<algorithm>

1. 统计元素出现的次数：count(iterator_begin,iterator_end,key)，大于 $0$ 则表示存在该元素

       #include<algorithm>
   
       vector<int> nums = { 4, 7, 9, 1, 2, 5 };
       int key = 2;
   
       if (count(nums.begin(), nums.end(), key)) //出现次数不为0
               cout << "存在元素" << endl;
   

2. 直接对数组查找：find(iterator_begin,iterator_end,key)，查找范围为 $[begin,end)$，其底层原理就是一一遍历

       #include<algorithm>
   
       vector<int> nums = { 1, 20, 2, 6, 3, 7 };
       int key = 6;
   
       if (find(nums.begin(), nums.end(), key) != nums.end())
           cout << "存在元素" << endl;
   

   这里与map中自带的$find()$函数不同

3. 还有一个原理与 $find$ 相同的函数 find_if(iterator_begin, iterator_end, pred)，只是它还可以配合 $lambda$ 函数进行更多的判断

       auto lst = {1,4,9,5,11};
       if(find_if(lst.begin(),lst.end(),[](auto v){
           if(v%5 ==0)
               return true;
           else
               return  false;
       }) != lst.end()){
           cout << "存在元素" << endl;
   

代码实现：

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
            unordered_map<int,int> hash;
            int n=nums.size();
            vector<int> res;
            for(int i=0;i<n;i++)
            {
                ++hash[nums[i]];
                //-------
                //时间复杂度为O(n^2)，这里只是想补充一下知识点
                if (hash[nums[i]]>n/3)
                {
                    auto it=find(res.begin(),res.end(),nums[i]);
                    if (it==res.end())
                        res.push_back(nums[i]);
                }
                //--------
            }
            时间复杂度为O(n)的做法：
            //for (auto & v : hash) {
            //    if (v.second > n / 3) {
            //        res.push_back(v.first);
            //    }
            //}
            return res;
    }
};

2.摩尔投票法(进阶)

算法实现

摩尔投票法：摩尔投票法的核心思想为对拼消耗，首先我们考虑最基本的摩尔投票问题，比如找出一组数字序列中出现次数大于总数 $\lfloor \frac{n}{2}\rfloor$​ 的数字（并且假设这个数字一定存在），如果我们令这个数字为阵营 $A$，其个数为阵营内的总人数，其他数字则均代表着挑战者，当出现一个挑战者时，阵营$A$中需要派出一名士兵与其对拼，他们将双双阵亡，最终，挑战者无一生还，而阵营$A$中则还有士兵，代表着他们镇守成功，也就证明了他们人数大于 $\lfloor \frac{n}{2}\rfloor$​

摩尔投票法进阶：现在我们考虑找出出现次数大于 $\lfloor \frac{n}{3}\rfloor$​ 的数，首先要知道，在任何数组中，出现次数大于该数组长度 $1/3$的值 $\le 2$，我们把它比作一场三方混战，战斗结果最多只有两个阵营幸存，挑战者全被歼灭：

• 我们维护两个潜在幸存阵营 $A$ 和 $B$：遍历数组，如果遇到了属于 $A$ 或者属于 $B$ 的士兵，则把士兵加入 $A$ 或 $B$ 队伍中，该队伍人数加一

• 当遇到了一个士兵既不属于 $A$ 阵营，也不属于 $B$ 阵营，这时有两种情况：

  1. a>0 && b>0：$A$ 阵营和 $B$ 阵营都还有活着的士兵，那么进行一次厮杀，$A$ 和 $B$ 两阵营为了公平起见，各派出一名士兵与其对拼，最终三个士兵全部阵亡，a--, b--

  2. a==0 || b==0：$A$ 阵营或 $B$ 阵营已经没有可以派出的士兵了，则没有士兵的阵营将被推翻，新士兵顶替它建立新的阵营

• 大战结束，最后 $A$ 和 $B$ 阵营即为初始人数最多的两大阵营，此时，双方争霸，最终决定以人数论英雄：如果其阵营的初始总人数没有超过 $\lfloor \frac{n}{3}\rfloor$​ ，将会被另一方斩杀，因此，还需再次遍历，检查其人数的合法性

图解算法：

推广结论：

1. 数组内出现次数超过 $\lfloor \frac{n}{k}\rfloor$​ 的数最多只有 $k-1$ 个
2. 若存在出现次数超过 $\lfloor \frac{n}{k}\rfloor$​ 的数，最后必然会成为这 $k-1$ 个候选者之一

代码实现：

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        vector<int> ans;
        int A,B;
        int vote1=0,vote2=0;
        //1.多方对战
        for(int i=0;i<nums.size();i++){
            if(vote1>0 && nums[i]==A) //A阵营来新人了
                vote1++;
            else if(vote2>0 && nums[i]==B) //B阵营来新人了
                vote2++;
            else if (vote1==0) //来的不是A阵营的
            {
                A=nums[i];
                vote1++;
            }
            else if (vote2==0) //来的不是B阵营的
            {
                B=nums[i];
                vote2++;
            }
            else if(vote1>0 && vote2>0) //来的既不是A，也不是B，但A,B仍可维持统治
            {
                vote1--;
                vote2--;
            }
        }

        //2.两方争霸
        vote1=0;vote2=0;
        for(auto num:nums){
            if (num==A)
                vote1++;
            if (num==B)
                vote2++;
        }
        if(vote1>nums.size()/3)
            ans.push_back(A);
        if(vote2>nums.size()/3 && A!=B) //防止A==B，如[0,0,0]
            ans.push_back(B);

        return ans;
    }
};

🍰15.三数之和

三数之和

👑思路分析

1.排序+双指针

算法实现

题目中要求找到所有 不重复 且和为 $0$ 的三元组，这个 不重复 的要求使得我们无法简单地使用三重循环枚举所有的三元组。这是因为在最坏的情况下，数组中的元素全部为 $0$:

[0, 0, 0, 0, 0, ..., 0, 0, 0]

此时，任意一个三元组的和都为 $0$，如果我们直接使用三重循环枚举三元组，会得到 $O(N^3)$ 个满足题目要求的三元组，时间复杂度至少为$:O(N^3)$，之后还需要使用哈希表进行去重操作，又消耗了大量的空间$:O(n)$，这个做法的时间复杂度和空间复杂度都很高，因此，我们需要找到破局之法：

不重复的本质是什么？

• 第二重循环枚举到的元素不小于当前第一重循环枚举到的元素
• 第三重循环枚举到的元素不小于当前第二重循环枚举到的元素

也就是说，对于三元组 $(a,b,c)$ 满足 $a\le b\le c$ ，保证了只有 $(a,b,c)$ 这个顺序会被枚举到，而 $(b,a,c)$、$(c,b,a)$ 这些重复的情况将不会出现

如何保证 $a\le b\le c$ ？

我们只需要对数组进行由小到大的排序即可，这样则满足了后面的元素一定不可能小于前面的元素：sort(nums.begin(),nums.end(),greater<int>())

同时，对于 $a,b,c$ 三个数而言，相邻两次枚举的值不能相同，否则也会造成重复

[-2, 0, 1, 1, 1, 2]
  ^  ^  ^  ^

我们使用三重循环枚举到的第一个三元组为 $(-2,0,1)$，如果第三重循环继续枚举下一个元素，那么仍然是三元组 $(0,1,2)$，将会产生重复，因此我们需要将第三重循环「跳到」下一个不相同的元素，即数组中的最后一个元素 $2$，枚举三元组 $(-2,0,2)$

如何摆脱三重循环带来的高时间复杂度 $O(n^3)$？

由先前排序带来的数组有序的特性，我们不难想到使用 双指针，对于待确定的三元组 $(a,b,c)$，对遍历得到的最小元素 $a$ 进行固定，$b,c$ 待定：

• 遍历数组，确定每一轮的 $a(=nums[i])$
• 如果 a>0：此时最小元素已经 $>0$，则 $0<a\le b\le c$，和不可能为 $0$，且之后一定不会再出现满足条件的三元组，因此直接返回结果
• 剪枝：i>0 && nums[i]==nums[i-1]，由上一轮的判断已经得出了该情况下的结果，跳过此轮
• 双指针：我们令 $L=i+1,R=n-1$，当 L<R 时，对当前的 $sum=nums[i]+nums[L]+nums[R]$ 进行判断：
  1. sum==0：满足条件，将当前三元组加入到结果中，再将双指 $L,R$ 同时向中间移动
  2. sum>0：值偏大了，由于最小值$a$固定，需要调整此时三元组中最大的数$c$：R--，然后去重
  3. sum<0：值偏小了，由于最小值$a$固定，最大值$c$无法上调，则调整中间值$b$：L++，然后去重

图解算法：

代码实现：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        int L,R; //双指针
        int n=nums.size();
        sort(nums.begin(),nums.end()); //对nums进行升序排序
        //遍历数组，作为三元组中的最小元素
        for(int i=0;i<n-2;i++){
            if (nums[i]>0) //如果最小元素都大于0，则不可能存在满足条件的三元组和为0
                return ans;
            if (i>0 && nums[i]==nums[i-1]) //剪枝
                continue;
            L=i+1;
            R=n-1;
            while(L<R)
            {
                int sum=nums[i]+nums[L]+nums[R];
                //1.满足条件
                if (sum==0)
                {
                    ans.push_back({nums[i],nums[L],nums[R]}); //插入三元组(a,b,c)
                    //跳过重复元素，防止重复
                    while(L<R && nums[L]==nums[L+1])
                        L++;
                    while(L<R && nums[R]==nums[R-1])
                        R--;
                    L++;
                    R--;
                }
                //2.值小了
                else if(sum<0)
                {
                    while(L<R && nums[L]==nums[L+1])
                        L++;
                    L++;
                }
                //3.值大了
                else if(sum>0)
                {
                    while(L<R && nums[R]==nums[R-1])
                        R--;
                    R--;
                }
            }
        }
        return ans;
    }
};

🍰18.四数之和

四数之和

👑思路分析

1.排序+双指针

算法实现

本题延续三数之和的算法思想，排序后，枚举 $nums[a]$ 作为第一个数，枚举 $nums[b]$ 作为第二个数，那么此时的问题就转化为找到另外两个数，使得 $nums[a]+nums[b]+nums[c]+nums[d]=target$，则可以用双指针进行搜索

for(int a=0; a<n-1; a++){
    1.剪枝
    2.三数之和
}

因此，这道题的难点在于如何进行 剪枝：

• 对于 $nums[a]$ 的剪枝：
  此时固定了前一个元素：nums[a]
  1. 当 $sum=nums[a]+nums[a+1]+nums[a+2]+nums[a+3]>target$ 时，由于已经进行排序，而当前最小的四个数之和已经超过 target，说明之后不会再找到满足条件的四个数了，直接 break
  2. 当 $sum=nums[a]+nums[n-3]+nums[n-2]+nums[n-1]<target$ 时，即当前最大的四数之和仍小于 target，则说明此时的 $nums[a]$ 较小，continue 到下一轮循环中
  3. 当 a > 0 && nums[a] == nums[a-1] 时，说明当前情况已经在前一个状态中计算过，无需重复计算，continue 至下一轮

• 对于 $nums[b]$ 的剪枝：
  此时固定了前两个元素：nums[a], nums[b]
  1. 当 $sum=nums[a]+nums[b]+nums[b+1]+nums[b+2]>target$ 时，表明当前状态下最小的四个数之和已经超过 target，直接 break
  2. 当 $sum=nums[a]+nums[b]+nums[n-2]+nums[n-1]<target$ 时，表明当前状态下最大的四数之和仍小于 target，continue 到下一轮循环中
  3. 当 b > a+1 && nums[b] == nums[b-1] 时，说明当前情况已经在前一个状态中计算过，无需重复计算，continue 至下一轮

🔺注意：$c++$ 中相加结果可能会超过 $32$ 位整数 (int) 范围：$[-2,147,483,648，2,147,483,647]$，又因为 $lo{g}_{10}(2147483648)\approx 9.33$，夹在 $[10^9，10^{10}]$ 之间，因此需要用 $64$ 位整数 (long long) 存储四数之和

代码实现：

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        //1.排序
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        int n = nums.size();

        //2.四数之和
        for(int a=0; a<n-3; a++){
            long long x = nums[a];
            if (a > 0 && x==nums[a-1]) continue;                            //剪枝1
            if (x + nums[a+1] + nums[a+2] +nums[a+3] > target) break;       //剪枝2
            if (x + nums[n-3] + nums[n-2] +nums[n-1] < target) continue;    //剪枝3

            //3.三数之和
            for(int b=a+1; b<n-2; b++){
                long long y = nums[b];
                if (b > a+1 && y==nums[b-1]) continue;                  //剪枝1
                if (x + y + nums[b+1] +nums[b+2] > target) break;       //剪枝2
                if (x + y + nums[n-2] +nums[n-1] < target) continue;    //剪枝3

                //4.双指针
                int c = b + 1, d = n-1;
                while (c < d) {
                    long long s = x + y + nums[c] + nums[d];
                    if (s > target)
                        d--;
                    else if (s < target)
                        c++;
                    else {
                        ans.push_back(vector<int>{nums[a], nums[b], nums[c], nums[d]});
                        for (c++; c < d && nums[c] == nums[c - 1]; c++); // 跳过重复数字
                        for (d--; d > c && nums[d] == nums[d + 1]; d--); // 跳过重复数字
                    }
                }
            }
        }
        return ans;
    }
};

🍰36.有效的数独

有效的数独

👑思路分析

1.哈希表 & 数组

算法实现

1.哈希表嵌套 $vector$

由于我们只需要判断每一行 $/$ 列 $/$ $3\times 3$方格中是否存在重复元素，因此我们可以定义哈希表对每一个元素的合法性进行精准判断：

• 将列、行、方格定义为 unordered_map<int,vector<int>> row,col,area：
  1. row[i]：记录第 $i$ 行所包含的元素
  2. col[j]：记录第 $j$ 列所包含的元素
  3. area[k]：记录第 $k$ 个方格中所包含的元素
• 遍历数独数组，当遍历到 '.' 时跳过；当遍历到有效字符时，利用$ASCII$码进行数据类型转换 $char\to int$：int tmp = board[i][j] -'0'
• 判断 $(i,j)$ 属于哪一个 $3\times 3$ 方格，可以求出映射公式为：

$方格序号k=3\ast$ $\lfloor \frac{i}{3}\rfloor$ $+$ $\lfloor \frac{j}{3}\rfloor$

• 只要行$/$列$/$方格中的一个出现有重复元素，则直接返回 false，否则就向当前行、列和方格对应的容器中添加当前元素 $tmp$

代码实现：

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        unordered_map<int,vector<int>> area,row,col;
        for(int i=0;i<9;i++){
            for (int j=0;j<9;j++){
                if(board[i][j]=='.')
                    continue;
                int k=3*(i/3)+j/3; //表示所在方格为第k个
                int tmp=board[i][j]-'0';
                if(find(row[i].begin(),row[i].end(),tmp)!=row[i].end() ||   //行不满足
                   find(col[j].begin(),col[j].end(),tmp)!=col[j].end() ||   //列不满足
                   find(area[k].begin(),area[k].end(),tmp)!=area[k].end())  //区域不满足
                    return false;
                else{
                    row[i].push_back(tmp);
                    col[j].push_back(tmp);
                    area[k].push_back(tmp);
                }
            }
        }
        return true;
    }
};

2.哈希表嵌套 $set$

思想同上，这里我们是为了学习 $c++$ 另一个 $STL$ 库：集合 $set$

关联容器——集合 $Set$
特点：

1. 集合内不会出现重复元素
2. 集合内的元素会依据其值自动排序$[升序]$

操作：

• 头文件$+$定义方式：

  #include<set>
  set<type> s;
  

• 插入：set.insert(val)

• 删除：set.erase(val)

• 统计：set.count(val) $(0/1)$

• 元素个数：set.size()

代码实现：

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        unordered_map<int,set<int>> area,row,col;
        for(int i=0;i<9;i++){
            for (int j=0;j<9;j++){
                if(board[i][j]=='.')
                    continue;
                int k=3*(i/3)+j/3; //表示所在方格为第k个
                int tmp=board[i][j]-'0';
                if(area[k].count(tmp) || row[i].count(tmp) || col[j].count(tmp)) //不满足
                    return false;
                area[k].insert(tmp);
                row[i].insert(tmp);
                col[j].insert(tmp);
            }
        }
        return true;
    }
};

3.数组

大多数的哈希表计数问题，都能转换为使用数组解决：虽然时间复杂度一样，但哈希表的更新和查询复杂度为平均 $O(1)$，而定长数组的的更新和查询复杂度则是严格 $O(1)$，因此从执行效率上来说，数组要比哈希表快上不少

我们先来看 $c++$ 中哈希表的底层原理：

事实上，unordered_map 中的$Key、Value$ 数据并不会直接存储在 $Hash$ 表的数组中，因为数组要求存储固定数据类型，主要目的是每个数组元素中要存放固定长度的数据，所以，数组中存储的是 $Key、Value$ 数据元素的地址指针，一旦发生 $Hash$ 冲突，只需要将相同下标，不同 $Key$ 的数据元素添加到这个链表就可以了，查找的时候再遍历这个链表，匹配正确的 $Key$，如下所示：

因为有 $Hash$ 冲突的存在，所以 $Hash$ 表在极端情况下，所有 $Key$ 的数组下标都冲突，那么 $Hash$ 表就会退化为一条链表，查询的时间复杂度是 $O(N)$

数组操作：

• 使用 $new$ 创建二维数组 $+$ $delete$ 释放：

    /*new创建数组*/
    //方法一:
    int (*p)[10] = new int[5][10];
  
    //方法二:
    int **p = new int* [5];
    for(int i=0;i <5;i++)
        p[i] = new int[10];
  

  /*delete释放空间*/
  for (int i = 0; i < 10; i ++) {
      delete[] array[i];
      array[i] = NULL;
      //不要忘记，释放空间后p[i]不会自动指向NULL值，还将守在原处，只是释放内存而已
  }
  delete [] array；
  array=NULL;
  

• 二维数组的初始化：

  1. 构造函数法：
     对$new$创建的数组，在其后加上$()$，即可初始化为 $0$：

   /*1.一维数组*/
   int *p = new int[10]();
  
   /*2.二维数组*/
   int (*p)[10] = new int [5][10]();
  

  2. $memset$ 法：
     memset 的使用注意：
     1. 二维整型数组利用$memset()$函数初始化时，只能初始化为 0/-1，否则二维整型数组的值将为随机数
     2. 二维char数组利用$memset()$函数初始化时不受限制，可初始化为任意字符

  memset(nums,0,sizeof(nums));
  

解释：

1. row[i][val]：表示第i行中val出现的次数
2. col[j][val]：表示第j列中val出现的次数
3. area[k][val]：表示第k个方格中val出现的次数

代码实现：

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        int (*area)[10]=new int[10][10]();
        int (*row)[10]=new int[10][10]();
        int (*col)[10]=new int[10][10]();

        for(int i=0;i<9;i++){
            for (int j=0;j<9;j++){
                if(board[i][j]=='.')
                    continue;
                int k=3*(i/3)+j/3; //表示所在方格为第k个
                int tmp=board[i][j]-'0';
                if(area[k][tmp] || row[i][tmp] || col[j][tmp]) //不满足
                    return false;
                area[k][tmp]++;
                row[i][tmp]++;
                col[j][tmp]++;
            }
        }
        return true;
    }
};

2.位运算压缩

算法实现

其实，我们还可以仅使用一个 $int$ 来记录 某行$/$某列$/$某个方块 的数值填入情况：

• 使用从低位开始的 $[1,9]$ 位来记录该数值是否已被填入$（0$为未填入，$1$为填入$）$
  例如 $(111000111{)}_2$ 代表数值 $[1,3]$ 和 $[7,9]$ 均被填入
• 若出现了一个新元素 x，则可以用二进制中的 或 操作更新当前行、列、方格的状态：
  例如 row[i] = row[i] | (1<<x)
• 判断当前行$/$列$/$方格是否出现过元素 x 时，可以用二进制中的 与 操作：
  例如 (row[i] >> u) & 1，若为 $1$，则表示出现过；否则未出现

代码实现：

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        int *area = new int[10]();
        int *row = new int[10]();
        int *col = new int[10]();

        for(int i=0;i<9;i++){
            for (int j=0;j<9;j++){
                if(board[i][j]=='.')
                    continue;
                int k=3*(i/3)+j/3; //表示所在方格为第k个
                int tmp=board[i][j]-'0';
                if( (area[k]>>tmp) & 1 == 1 ||
                    (row[i]>>tmp)  & 1 == 1 ||
                    (col[j]>>tmp)  & 1 == 1 )
                    return false;
                area[k] |= (1<<tmp);
                row[i] |= (1<<tmp);
                col[j] |= (1<<tmp);
            }
        }
        return true;
    }
};

🍰48.旋转图像

旋转图像

👑思路分析

1.辅助数组

算法实现

对于一个矩阵，我们先分析它旋转之后各个元素会出现在什么位置：

$$\left(\begin{array}{cccc}5& 1& 9& 11\\ 2& 4& 8& 10\\ 13& 3& 6& 7\\ 15& 14& 12& 16\end{array}\right)$$

我们对第一行进行旋转：

$$\left(\begin{array}{cccc}5& 1& 9& 11\\ o& o& o& o\\ o& o& o& o\\ o& o& o& o\end{array}\right)\to \left(\begin{array}{cccc}o& o& o& 5\\ o& o& o& 1\\ o& o& o& 9\\ o& o& o& 11\end{array}\right)$$

可以发现，第一行的元素整体旋转后会到最后一列，且数字内部的顺序保持不变$($左$\to$右、上$\to$下$)$

我们再对第二行进行旋转：

$$\left(\begin{array}{cccc}o& o& o& o\\ 2& 4& 8& 10\\ o& o& o& o\\ o& o& o& o\end{array}\right)\to \left(\begin{array}{cccc}o& o& 2& o\\ o& o& 4& o\\ o& o& 8& o\\ o& o& 10& o\end{array}\right)$$

第二行旋转后出现在倒数第二列上，且原来在第 $k$ 列上的数字变到了第 $k$ 行上

对于矩阵中第 $i$ 行的第 $j$ 个元素，在旋转后，它出现在倒数第 $i$ 列的第 $j$ 个位置

因此，我们可以构造一个辅助数组存放旋转后的数组 matrix_new，令 matrix_new[j][n-i-1]=matrix[i][j]，最后将$matri{x}_{n}ew$的值拷贝给$matrix$即可

二维 $vector$ 部分操作实现：

• 初始化二维$vector$:

  vector<vector<int>> matrix(n,vector(m,0));
  

• 获取二维$vector$容器的大小时:

  //1.获取行数
  int n=matrix.size();
  //2.获取列数
  int m=matrix[0].size();
  

代码实现：

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n=matrix.size();
        vector<vector<int>> matrix_new(n,vector<int>(n,0));    //初始化辅助数组
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                matrix_new[j][n-i-1]=matrix[i][j]; //第i行旋转后变为第n-i列
            }
        }
        matrix=matrix_new; //直接拷贝
    }
};

2.原地旋转

算法实现

题目中要求我们尝试在不使用额外内存空间的情况下进行矩阵的旋转，也就是说，我们需要「原地旋转」这个矩阵，我们注意到方法一中有一个很重要的 映射关系：

$matrix[row][col]\to matrix\_new[col][n-row-1]$

我们设想，假设对某一点进行旋转处理，我们不能直接令 $matrix\_new[col][n-row-1]=matrix[row][col]$，这样会导致对 $[col][n-row-1]$ 位置上的数据进行覆盖，因此，我们需要使用一个变量 tmp 保存它，那么此时，当我们继续对原本在 $[col][n-row-1]$ 上的数据进行旋转时，它又会转到哪里呢？

利用 映射关系，可以推导：

$$\{\begin{array}{l}第一次旋转：ne{w}^0[row][col]\to ne{w}^1[col][n-row-1]\\ 第二次旋转：ne{w}^1[col][n-row-1]\to ne{w}^2[n-row-1][n-col-1]\\ 第一次旋转：ne{w}^2[n-row-1][n-col-1]\to ne{w}^3[n-col-1][row]\\ 第一次旋转：ne{w}^3[n-col-1][row]\to ne{w}^4[row][col]\end{array}$$

所以，当旋转四次后，有 new4==new0，也就是回到了初始点，当我们根据一个点就可以旋转四个点时，我们可以将矩阵分为四块，我们只需要遍历其中的一块上的所有点并对其进行四次旋转操作，就可以将整个矩阵旋转

• 每一轮旋转只需要记录一次 tmp：$(也可以调整顺序)$
  

• $①$ 当 $n$ 为偶数时，只需要遍历 $\frac{n^2}{4}=\frac{n}{2}$×$\frac{n}{2}$ 个点，可以等分为四个 $\frac{n}{2}$×$\frac{n}{2}$ 区域：
  $②$ 当 $n$ 为奇数时，需要遍历 $\frac{n^2-1}{4}=\frac{n-1}{2}$×$\frac{n+1}{2}$ 个点，即等分为四个 $\frac{n-1}{2}$×$\frac{n+1}{2}$ 区域：

  

代码实现：

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n=matrix.size();
        for(int i=0;i<n/2;i++){
            for(int j=0;j<(n+1)/2;j++){
                int tmp=matrix[j][n-i-1];                   //记录b
                matrix[j][n-i-1]=matrix[i][j];              //a->b
                matrix[i][j]=matrix[n-j-1][i];              //d->a
                matrix[n-j-1][i]=matrix[n-i-1][n-j-1];      //c->d
                matrix[n-i-1][n-j-1]=tmp;                   //b->c
            }
        }
    }
};

3.翻转代替

算法实现

还是根据旋转的 映射关系：

$matrix[row][col]\to matrix\_new[col][n-row-1]$

我们可以根据其坐标变换特性将其拆解为两步：

1. 上下对称翻转：$matrix[row][col]\to matrix[n-row-1][col]$，我们只需遍历矩阵的上半部分所有点

$$\left(\begin{array}{ccccc}5& 1& 9& 11& \\ 2& 4& 8& 10& \\ --& --& --& --& \\ 13& 3& 6& 7& \\ 15& 14& 12& 16& \end{array}\right)\to \left(\begin{array}{ccccc}15& 14& 12& 16& \\ 13& 3& 6& 7& \\ --& --& --& --& \\ 2& 4& 8& 10& \\ 5& 1& 9& 11& \end{array}\right)$$

2. 沿主对角线对称翻转：$matrix[n-row-1][col]\to matrix[col][n-row-1]$，我们只需遍历矩阵的上三角部分所有点

由于每一次翻转都需要遍历矩阵一半的点，所以时间复杂度为$：O(n^2)$

代码实现：

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n=matrix.size();
        //1.上下对称翻转
        for(int i=0;i<n/2;i++){
            for(int j=0;j<n;j++){
                swap(matrix[i][j],matrix[n-i-1][j]);
            }
        }
        //2.主对角线翻转
        for(int i=0;i<n-1;i++){
            for(int j=i+1;j<n;j++){
                swap(matrix[i][j],matrix[j][i]);
            }
        }
    }
};

🍰54.螺旋矩阵

螺旋矩阵

👑思路分析

1.按层模拟

算法实现

①常规版：

可以将矩阵看成若干层，首先输出最外层的元素，其次输出次外层的元素，直到输出最内层的元素，像洋葱一样一层一层地剥开

• 定义一个参数 k，以此限定边框的范围，初始化为：k=0

• 对于 m*n 阶矩阵，最外层$($第 $1$ 层$)$的边框范围：$i\in [0,m-1]，j\in [0,n-1]$，第 $2$ 层的边框范围：$i\in [1,m-2]，j\in [1,n-2]$ $...$ 我们发现，每当边框向内缩小一层时，其行$、$列的区间左右界限会各自减 1

• 由此得出，若每遍历完一层后都缩小一次边框：k--，则 对于第 $k$ 层而言，其边框的范围为：

$i\in [k,m-k-1]，j\in [k,n-k-1]$

• 由于遍历每一层边框时，都遵循 “$左\to 右,上\to 下,右\to 左,下\to 上$”，因此，我们将边框分为 “上、下、左、右” 四个部分，并且要确保不重复遍历，所以当遍历完每个角时，需要再移动一格，再继续遍历下一个边框：

$$\{\begin{array}{l}上：i=k，j\in k\to n-k-1\\ 右：j=n-k-1，i\in k+1\to m-k-1\\ 下：i=m-k-1，j\in n-k-2\to k\\ 左：j=k，i\in m-k-2\to k+1\end{array}$$

• 我们用一个 count 记录遍历的元素个数，当 count>=n*m 时遍历结束

图解算法：

代码实现：

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m=matrix.size();    //行数
        int n=matrix[0].size(); //列数
        int N=m*n;              //总数
        int count=0;        //记录走过的数的个数
        vector<int> res;
        int i=0,j=0,k=0;
        while(true){
            //上边框
            for(;j<n-k;j++){
                res.push_back(matrix[i][j]);
                count++;
                if(count>=N) return res;
            }
            j--;    //回溯
            i++;    //向下走一步

            //右边框
            for(;i<m-k;i++){
                res.push_back(matrix[i][j]);
                count++;
                if(count>=N) return res;
            }
            i--;    //回溯
            j--;    //向左走一步

            //下边框
            for(;j>=k;j--){
                res.push_back(matrix[i][j]);
                count++;
                if(count>=N) return res;
            }
            j++;    //回溯
            i--;    //向上走一步

            //左边框
            for(;i>=k+1;i--){
                res.push_back(matrix[i][j]);
                count++;
                if(count>=N) return res;
            }
            i++;    //回溯
            j++;    //向内走一步
            k++;    //边框范围缩小
        }
    }
};

②进阶版：

我们也可以根据上面的思路让代码更简洁一点，设定 上、下、左、右 四个边界为 $t,b,l,r$，每遍历完某一个方向的边框后，就缩小一次该方向的边界值，当边界值出现 $t(上)<b(下)$ 或 $r(右)<l(左)$ 时，结束遍历：

代码实现：

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if (matrix.empty())
            return {};
        int l = 0, r = matrix[0].size() - 1, t = 0, b = matrix.size() - 1;
        vector<int> res;
        while (true) {
            for (int i = l; i <= r; i++) res.push_back(matrix[t][i]); // left to right
            if (++t > b) break;
            for (int i = t; i <= b; i++) res.push_back(matrix[i][r]); // top to bottom
            if (l > --r) break;
            for (int i = r; i >= l; i--) res.push_back(matrix[b][i]); // right to left
            if (t > --b) break;
            for (int i = b; i >= t; i--) res.push_back(matrix[i][l]); // bottom to top
            if (++l > r) break;
        }
        return res;
    }
};

🍰56.合并区间

合并区间

👑思路分析

1.排序+双指针

算法实现

首先，对于二维 $vector$ 中存放的无序区间，我们需要对其进行排序，根据区间左值进行升序排列，也就是满足 $intervals[i][0]\le intervals[i+1][0]\le ...$

二维 $vector$ 的排序：

• 自定义排序函数：

    static bool cmp(const vector<int>& a,const vector<int>& b){
        return a.back()<b.back();
    }
  
    vector<vector<int>> nums;
    sort(nums.begin(),nums.end(),cmp);
  

• $lambda$ 函数：

    sort(nums.begin(),nums.end(),[](vector<int>a, vector<int>b){
        return a[0]<b[0]; //根据第一个关键字值进行升序排序
    });
    // return a[1]<b[1] 实现二维数组中第二个关键字的排序
  

其次，我们需要考虑什么情况下会发生区间合并，假设现在有已排序的二维 $vector$：

$[[1,3],[2,6],[3,5],[10,12]]$

我们容易发现，$[1,3],[2,6]$ 可以合并为 $[1,6]$，这是因为 区间 $[2,6]$ 的最小值 2 小于区间 $[1,3]$ 的最大值 3，所以两区间必有交集，因此可以合并为 $[1,6]$，此时的区间最大值变为 6

再继续观察下一个区间 $[3,5]$，由于其区间最小值 3 小于 $[1,6]$ 的最大值 6，所以也可以被合并，并且合并后区间的最大值 M=max(6,5)，所以区间最大值不变，由于已经排好序，区间最小值一定不会改变，则合并为 $[1,6]$

观察最后一个区间 $[10,12]$，我们发现此时的区间最小值 10 大于 $[1,6]$ 的最大值 6，所以二者没有交集，无法合并，所以最终结果为：

$[[1,6],[10,12]]$

双指针优化：

• 两个区间 $[min,Max],[start,end]$ 合并条件为：start ≤ M
• 对于上述过程，我们不需要一个一个合并，可以定义两个指针 $i,j$，并用M维护当前区间的最大值：
  1. $i$ 用于维护当前待合并区间的最小值$（区间左值）$
  2. $j$ 用于找到以 $i$ 为最小值的可合并区间的最大位置
  3. $M$ 用于维护当前待合并区间的最大值$（区间右值）$
• 遍历整个数组，依次判断是否满足 合并条件：
  1. 可以合并：$i$ 不动，更新 $M$，$j$ 继续移动
  2. 无法合并：获得以 $i$ 为最小值的最大合并区间 [i,M]，令i=j，$j$ 继续移动

图解算法

代码实现：

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        //1.排序
        sort(intervals.begin(),intervals.end(),[](const vector<int>& a,const vector<int>& b){
            return a[0]<b[0]; //由第一个关键字值实现升序排列
        });
        //2.双指针
        vector<vector<int>> ans;
        for(int i=0;i<intervals.size();){
            int j=i+1;
            int M=intervals[i][1];  //记录右边界最大值
            while(j<intervals.size() && intervals[j][0]<=M){
                M=max(intervals[j][1],M);
                j++;
            }
            ans.push_back({intervals[i][0],M});
            i=j;
        }
        return ans;
    }
};

🍰75.颜色分类

颜色分类

👑思路分析

1.单指针

算法实现：

最简单的方法就是进行两次遍历，先后对 $0、1$ 进行排序，在经过两趟处理后，$2$ 自然也已经排好序了:

• 定义一个指针 $p$，表示当前要找的元素应该放入的位置，初始化 p=0
• 第一趟遍历：找到所有的 $0$
  1. 从 i=0 遍历数组，当存在元素 nums[i]==0 时，由于此时 $p$ 为元素 $0$ 待插入的位置，因此交换 $nums[i]$ 和 $nums[p]$
  2. 当找到一个 $0$ 时，p++ (表示如果数组内还存在元素 $0$ 则插在下一个位置)
• 第二趟遍历：找到所有的 $1$
  1. 由于数组的 $[0,p-1]$ 部分已经存放了数组内所有的 $0$，而在上一次遍历结束时，p++ 指向了数组内所有连续 $0$ 之后的第一个位置，因此，此时的指针 $p$ 为元素 $1$ 的待插入位置
  2. 从 j=p 遍历数组，当存在元素 nums[j]==1 时，交换 $nums[j]$ 和 $nums[p]$
  3. 当找到一个 $1$ 时，p++

图解算法：

代码实现：

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n=nums.size();
        int p=0;
        //第一趟找到所有的0
        for(int i=0;i<n;i++){
            if (nums[i]==0){
                swap(nums[p], nums[i]);
                p++;
            }
        }
        //此时p指向所有连续0之后的第一个位置
        //第二趟找到所有的1
        for(int j=p;j<n;j++){
            if (nums[j]==1){
                swap(nums[p], nums[j]);
                p++;
            }
        }
    }
};

2.计数法

算法实现：

基于单指针的方法思路，我们不难发现，只需要统计出 $0,1$ 各自在数组中出现的次数，就可以按区间给数组进行赋值，从而得到排序数组:

• 第一趟遍历：统计 $0,1$ 出现的次数 $cnt1,cnt2$
• 第二趟遍历：基于得到的统计结果，将数组划分为三个部分 $[0,cnt1-1]$, $[cnt1,cnt1+cnt2-1]$, $[cnt1+cnt2,n-1]$，对三个区间分别赋值为 $0,1,2$

代码实现：

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n=nums.size();
        int cnt1 = 0, cnt2 = 0;
        //第一次循环
        for(int i = 0; i<n; i++){
            if (nums[i]==0) cnt1++;
            if (nums[i]==1) cnt2++;
        }

        //第二次循环
        for(int i = 0; i<n; i++){
            if (i<cnt1)
                nums[i]=0;
            else if (i<cnt1+cnt2)
                nums[i]=1;
            else
                nums[i]=2;
        }
    }
};

3.双指针

算法实现：

以上两种算法都需要遍历两次，那么能不能只遍历一次就得到结果呢？

我们可以定义两个指针：$p_0，p_2$，分别表示当前 $0$ 和 $2$ 应该放入的位置，$p_0$ 从左向右移动，$p_2$ 从右向左移动；再定义一个变量 $i$ 表示当前待比较元素的位置

• 初始时，p0=i=0，p2=n-1
• 由于指针 $p_0$ 一定慢于 $i$，因此，当 $[0,i]\cup [p_2,n-1]$ 能够表示当前已经访问过的数组元素的区间，当 $i\le p_2$ 时:
  1. nums[i]==2：交换 $nums[i]$ 与 $nums[p_2]$，使得 $p_2$ 位置放入元素 $2$，p2--，循环此操作，直到 $nums[i]\ne 2$，继续下一个判断；
  2. nums[i]==0：交换 $nums[i]$ 与 $nums[p_0]$，使得 $p_0$ 位置放入元素 $0$，p0++；
  3. nums[i]==1：不做处理
  4. 当前位置元素比较结束，继续下一个元素的比较：i++

为什么需要循环直到 $nums[i]\ne 2$？

因为交换后可能出现 $nums[i]$ 仍为 $2$ 的情况，如果不循环处理，则会继续判断 $nums[i]$ 是否为 $0$，此时显然不为 $0$，于是会将 $i$ 移向下一个位置 $nums[i+1]$，这样有可能会导致结果出错：

1. 结果仍正确：
   后面必然元素 $0$，因为有 $0$ 则意味着可以通过交换 $nums[p_0]$ 和 $nums[i]$ 改变元素 $2$ 的位置$（$如 $[2,0,2]$ $）$
2. 结果出错：
   后面可能有 $0$ 也可能没有，这不是必要条件$（$如 $[1,1,0,2,2]$ $）$

可以将上述 nums[i]==2 中的循环去掉自行尝试

图解算法：

代码实现：

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n=nums.size();
        int p0 = 0;     //0插入的位置
        int p2 = n-1;   //2插入的位置
        int i = 0;      //待比较的位置
        while(i<=p2){
            //1.判断2
            while(i<=p2 && nums[i]==2){
                swap(nums[i],nums[p2]);
                p2--;
            }
            //2.判断0
            if (nums[i]==0){
                swap(nums[i],nums[p0]);
                p0++;
            }
            i++;
        }
    }
};

4.刷油漆法

算法实现：

背景介绍：

假设现在要刷一面墙，老板最开始对你说：把墙全部刷成蓝色就好！于是，你将整个墙壁全部刷上了蓝色；
之后，老板又说：太单调了，还是把左边部分刷成白色吧！于是，你用白色颜料覆盖了左边部分的蓝色；
最后，老板思来想去，又对你说：还是不太好看，你把白色部分的左边部分刷成红色吧！于是，你在刷了三次墙后，终于达到了老板满意的效果

如果将蓝色、白色、红色分别对应题目中的 $2，1，0$，那么可以类比为：

• 遍历数组，记录当前元素的值 $val$ 后，将当前位置涂成蓝色（ ${}^{\prime }{2}^{\prime }$），开始判断
• 若 val<2，则用白色覆盖当前位置原本的蓝色（${}^{\prime }{2}^{\prime }$），即 将当前位置涂成 ${}^{\prime }{1}^{\prime }$，继续判断
• 若 val<1，则继续用红色覆盖当前位置原本的白色（${}^{\prime }{1}^{\prime }$），即 将当前位置涂成 ${}^{\prime }{0}^{\prime }$

图解算法：

当然，具体算法的实现仍是基于双指针：定义两个指针 $p_0$ 和 $p_1$：分别表示 $0$ 和 $1$ 的待涂位置，由于连续的 ${}^{\prime }{1}^{\prime }$ 必然在 连续的 ${}^{\prime }{0}^{\prime }$ 之后，所以理论上，$p_1$ 应该会超前于 $p_0$，也就是p1 ≥ p0

而对于刷油漆算法而言，正好巧妙地解决了这一点：

• 若要涂成 ${}^{\prime }{2}^{\prime }$，则 $p_0，p_1$ 都不移动
• 若要涂成 ${}^{\prime }{1}^{\prime }$，则 $p_1$ 移动一步；
• 若要涂成 ${}^{\prime }{0}^{\prime }$，则 $p_1$ 会先移动一步，之后 $p_0$ 再移动一步

这就可以保证一直满足 p1 ≥ p0，换句话说，$p_0$ 与 $p_1$ 已经自然地将数组分为了三个部分：

$[0,p_0-1]\cup [p_0,p_1-1]\cup [p_1,n-1]$

而这三个区间对应的数分别是 $0，1，2$

刷油漆代码实现：

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n=nums.size();
        int p0 = 0;
        int p1 = 0;
        for(int i=0; i<n; i++){
            int val = nums[i];
            nums[i] = 2;        //先刷成2
            if (val<2)
                nums[p1++] = 1; //<2刷成1
            if (val<1)
                nums[p0++] = 0; //<1刷成0
        }
    }
};

双指针代码实现：

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n = nums.size();
        int p0 = 0;
        int p1 = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 1) {
                swap(nums[i], nums[p1]);
                ++p1;
            }
            else if (nums[i] == 0) {
                swap(nums[i], nums[p0]);
                if (p0 < p1) {
                    swap(nums[i], nums[p1]);
                }
                ++p0;
                ++p1;   //用双指针的方法，p1在两种情况下都需要移动
            }
        }
    }
};

🍰162.寻找峰值

寻找峰值

👑思路分析

1.暴力法

算法实现：

由于要找到严格大于左右两边的任意一个峰值，因此，最简单的实现就是枚举每一个元素，比较其与两边值的大小，满足则直接返回，时间复杂度为 $O(n)$：

• 首尾元素特殊处理：由于题目给定条件 $nums[-1]=nums[n]=-\infty$，因此：
  1. i==0，满足 $nums[0]>nums[1]$ 则返回
  2. i==n-1，满足 $nums[n-1]>nums[n-2]$ 则返回
• 其他元素一般处理：nums[i]>nums[i-1] && nums[i]>nums[i+1] 则返回当前下标

注意：在枚举之前，需要进行一个预处理，即判断数组大小是否为 $1$，若为 $1$，则直接返回峰值元素下标为 $0$，这样避免了数组下标访问越界的情况

代码实现：

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int n = nums.size();
        if (n==1)
            return 0;
        for(int i=0; i<n; i++){
            if (i==0){
                if (nums[i]>nums[i+1])
                    return i;
            } else if (i==n-1){
                if (nums[i]>nums[i-1])
                    return i;
            } else{
                if (nums[i]>nums[i-1] && nums[i]>nums[i+1])
                    return i;
            }
        }
        //没有找到
        return NULL;
    }
};

2.利用vector容器函数求解

算法实现：

对于 vector<int> nums，有常用函数 max_element 和 min_element 可以求得容器中的最大$/$最小值，函数的时间复杂度为 $O(n)$：

• 头文件

  #include <algorithm>
  

• 参数与返回值

  1. max_element(first, last)：其中 $fist$ 和 $last$ 分别表示开始迭代器和结束迭代器，即定义了一个要检测范围的向前迭代器 $[first,end)$
  2. 返回值为指向范围 $[first,last)$ 中最大元素的迭代器：
     $①$ 若范围中有多个元素等价于最小元素，则返回指向首个这种元素的迭代器
     $②$ 若范围为空则返回 $last$

有哪些用途呢？

1. 求解 最大值
   返回值为迭代器，则可以利用 * 对返回的迭代器进行解引用，从而得到最大值

    vector<int> n;
    int maxV = *max_element(n.begin(),n.end()); //最大值
    int minV = *min_element(n.begin(),n.end()); //最小值
   

2. 求解 最大值对应的下标
   由于返回值是一个迭代器，因此我们可以用返回的迭代器与容器的开始迭代器 nums.begin() 相减，来计算他们之间的偏移量，也就是最大值对应的下标

    int maxPosition = max_element(n.begin(),n.end()) - n.begin(); //最大值下标
    int minPosition = min_element(n.begin(),n.end()) - n.begin(); //最小值下标
   

代码实现：

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        //迭代器相减得到峰值下标
        return max_element(nums.begin(), nums.end()) - nums.begin();
    }
};

3.迭代爬坡法

算法实现：

迭代爬坡法的核心思想就是模拟爬坡的过程，当我们身处山的某一处时，判断一下我们左右两边的海拔高度，然后选择往高处走，从而达到山峰

现假设你降落到了山的某一处 idx = rand() % n：

1. 如果 nums[idx] > nums[idx-1] && nums，那么恭喜你，降落到了一个山峰，不用爬啦
2. 如果 nums[idx] < nums[idx+1]，你降落到了山腰，应该向右爬
3. 如果 nums[idx] < nums[idx-1]，你降落到了山腰，应该向左爬
4. 如果 nums[idx] < nums[idx-1] && nums[idx] <nums[idx+1]，那么很遗憾，你掉到了山谷中，已经是最低处了，随便选一边开始爬吧

🔺值得注意的是，为了使操作统一，这里选择使用 $c++$ 中的 pair：

• 定义： $pair$ 将两个数据合为一个，可以理解为一个二元组，也可以理解为一个键值对

• 头文件

  #include <utility>
  

• 类模板：template<class T1,class T2> struct pair

• 解释：$pair$ 的实现是一个结构体，主要的两个成员变量是 $first，second$，可以通过 p.first 和 p.second 进行访问

• 各种操作

    pair<T1, T2> p1;            // 创建一个空的pair对象（使用默认构造），它的两个元素分别是T1和T2类型，采用值初始化
    pair<T1, T2> p1(v1, v2);    // 创建一个pair对象，它的两个元素分别是T1和T2类型，其中first成员初始化为v1，second成员初始化为v2
    make_pair(v1, v2);          // 以v1和v2的值创建一个新的pair对象，其元素类型分别是v1和v2的类型
    p1 < p2;                    // 两个pair对象间的小于运算，其定义遵循字典次序：如 p1.first < p2.first 或者 p2.first == p1.first && (p1.second < p2.second) 则返回true
    p1 == p2；                  // 如果两个对象的first和second依次相等，则这两个对象相等；该运算使用元素的==操作符
    p1.first;                   // 返回对象p1中名为first的公有数据成员
    p1.second;                  // 返回对象p1中名为second的公有数据成员
  

我们令悬崖处为 $p_0=(0,0)$，其他地方为 $p_1=(1,nums[idx])$，这样就保证了在比较大小时，悬崖处的 p0.first < p1.first，即满足山体各处一定比两边的悬崖高

代码实现：

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int n = nums.size();
        int idx = rand() % n;

        //定义一个lambda函数
        auto height = [&](int i) -> pair<int, int>{
            if (i==-1 || i==n)
                return {0, 0};
            return {1, nums[i]};
        };

        //爬坡
        while(!(height(idx) > height(idx - 1) && height(idx) > height(idx + 1))){
            if (height(idx) < height(idx + 1))
                idx++;
            else
                idx--;
        }
        return idx;
    }
};

4.二分法

算法实现：

我们先来回顾一下 二分法：

1. 我们要确定一个区间 $[L,R]$
2. 我们要找到一个性质，并且该性质满足一下两点：
   1. 满足二段性
   2. 答案是二段性的分界点

也就是说，如果在确保有解的情况下，我们可以根据当前的分割点 $mid$ 与左右元素的大小关系来直到 $l$ 或 $r$ 移动

整数域二分模版分析：

①模版一：

当$ans$属于左边界时，这种情况下划分为两个区间 $[L，mid]\cup [mid+1，R]$，需要根据条件将某一般区间进行舍去:

1. 当 $mid$ 位于 $ans$ 的左侧时(红色区域)：$mid1$ 是有可能等于 $ans$ 的，为了避免我们将 $ans$ 排除在区间外，我们令 L = mid，从而在除去左边不需要的数据同时，还保证了 $ans$ 仍在区间内
2. 当 $mid$ 位于 $ans$ 的右侧时(蓝色区域)：$mid2$ 是无法等于 $ans$ 的，因此可以直接将 $mid2$ 以及右边的区域全部除去，令 R = mid-1

模版一代码：

while (l<r>){
    int mid = (l+r+1)>>1;
    if (在红色区域内)
        l = mid;
    else
        r = mid-1;
}
return r;

为什么这里是 $mid=(l+r+1)/2$ 呢？

取临界条件： $L=R-1$，在当前情况下，由于 $ans$ 位于左边界，应该让 $R$ 跨越到左区域（从而达到 L=R 以跳出循环）
而如果是 $mid=(l+r)/2$，那么 mid=L; L=mid，则仍有 $L=R-1$，因此将陷入局部死循环中无法跳脱，所以我们需要对 mid 进行向上取整

②模版二：

当$ans$属于右边界时，这种情况下将区间划分为 $[L，mid-1]\cup [mid，R]$：

1. 当 $mid$ 位于 $ans$ 的左侧时：由于此时 $mid1$ 不可能等于 $ans$，所以将 $mid1$ 及其左边部分全部舍去，令 L = mid+1
2. 当 $mid$ 位于 $ans$ 的右侧时：此时 $mid1$ 有可能等于 $ans$，所以为了避免 $ans$ 被跳过，令 R = mid

模版二代码：

while (l<r>){
    int mid = (l+r)>>1;
    if (在蓝色区域内)
        r = mid;
    else
        l = mid+1;
}
return r;

为什么这里又变为 $mid=(l+r)/2$ 呢？

取临界条件： $L=R-1$，在当前情况下，由于 $ans$ 位于右边界，应该让 $L$ 跨越到右区域（以达到 L=R 从而跳出循环）
而如果是 $mid=(l+r+1)/2$，那么 mid=R; R=mid，则仍有 $L=R-1$，所以我们需要对 mid 进行向下取整

总结：

我们强调，二分的本质是「二段性」而非「单调性」，而经过本题，我们进一步发现「二段性」还能继续细分，不仅仅只有满足 $01$ 特性（满足/不满足）的「二段性」可以使用二分，满足 $1?$ 特性（一定满足/不一定满足）也可以二分

二分法在本题中的应用：

回到本题，对于二分查找峰值，我们有两种逼近方法：

1. 从左向右逼近：
   此时，峰值 $ans$ 为左边界，采用上述 模板一
   

   当 nums[mid]>nums[mid-1] 时，则峰值可能为 $mid$ 或在 $mid$ 的右侧，令 l = mid
   当 nums[mid]<nums[mid-1] 时，则峰值必然在 $mid$ 的左侧，令 r = mid-1

2. 从右向左逼近：
   此时，峰值 $ans$ 为右边界，采用上述 模板二
   

   当 nums[mid]>nums[mid+1] 时，则峰值可能为 $mid$ 或在 $mid$ 的左侧，令 r = mid
   当 nums[mid]<nums[mid+1] 时，则峰值必然在 $mid$ 的右侧，令 l = mid+1

代码实现：

方法 1

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int n = nums.size();
        int l=0, r=n-1;
        while(l<r){
            int mid = (l+r+1)>>1;
            if (nums[mid]>nums[mid-1]) //ans在mid右侧
                l = mid;
            else                       //ans在mid左侧
                r = mid-1;
        }
        return r;
    }
};

方法 2

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int n = nums.size();
        int l=0, r=n-1;
        while(l<r){
            int mid = (l+r)>>1;
            if (nums[mid]>nums[mid+1]) //ans在mid左侧
                r = mid;
            else                       //ans在mid右侧
                l = mid+1;
        }
        return r;
    }
};

🍰189.轮转数组

轮转数组

👑思路分析

1.三次数组逆置

算法实现：

这是一道十分经典的题目（408真题），这里着重讲解空间复杂度为 $O(1)$ 的做法

题目要求数组左移 $k$ 位：

$(X_0,X_1,...,X_{n-1})\to (X_p,X_{p+1},...,X_{n-1},X_0,X_1,...,X_{p-1})$

因此可以得到 $p=n-k$，其中 p 表示 旋转分割线处 的下标，其中旋转分割线将原始数组分为了 $a,b$ 两个部分，$a,b$ 两部分将关于旋转分割线左右互换位置：$ab\to ba$

而要从状态 $ab\to ba$，可以联想到矩阵的逆

也就是说，分别对 $a，b$ 求逆：$a=a^{-1}，b=b^{-1}$，我们得到了两个部分逆置后的数组，最后再对当前数组整体求逆即可：$(a^{-1}{b}^{-1}{)}^{-1}=ba$

图解算法：

1. 原始数组与目标数组的确定
   

2. $a=a^{-1}$
   

3. $b=b^{-1}$
   

4. $(a^{-1}{b}^{-1}{)}^{-1}$
   

代码实现：

class Solution {
public:
    void Reverse(vector<int>& nums, int left, int right){
        for(int i=0; i<=(right-left)/2; i++)
            swap(nums[left+i], nums[right-i]);
    }

    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k = k % n;          //将k压缩到[0,n-1]区间
        int p = n - k;      //分割线处的下标

        //三次逆置
        if (p!= n){
            Reverse(nums, 0, p-1);
            Reverse(nums, p, n-1);
            Reverse(nums, 0, n-1);
        }
    }
};

🍰384.打乱数组

打乱数组

👑思路分析

1.Knuth洗牌算法

算法实现：

共有 $n$ 个不同的数，根据每个位置能够选择什么数，共有 $n!$ 种组合

现要求等概率地得到这 $n!$ 种组合，则可以使用 $Knuth$ 洗牌算法实现：

洗牌算法：每个数都有相等的概率被放到任意一个位置中，即每个位置中出现任意一个数的概率都是相同的

• 由第 $1$ 个位置到最后，依次从当前元素到最后一个元素中，随机选取一个元素与当前位置上的元素进行交换，通过 i + rand() % (n-i) 实现
• 假设假设有 $n$ 个元素，每个元素出现在第 $1$ 个位置的概率是 $\frac{1}{n}$​，依次类推，每个元素出现在第 $i$ 个位置（ $i$ 从 $1$ 开始）上的概率是：

$P=$ $\frac{n-1}{n}\times \frac{n-2}{n-1}\times ...\times \frac{1}{n-i+1}$ $=$ $\frac{1}{n}$

图解算法：

代码实现：

class Solution {
public:
    Solution(vector<int>& nums) {
        num = nums;
    }

    vector<int> reset() {
        return num;
    }

    vector<int> shuffle() {
        vector<int> nums(num); //用原数组初始化新数组
        int n = nums.size();

        for(int i=0; i<n; i++)
            swap(nums[i], nums[i + rand() % (n-i)]);

        return nums;
    }

private:
    vector<int> num;
};

🍰454.四数相加 II

四数相加II

👑思路分析

1.分组+哈希表

算法实现：

首先思考为什么要进行分组？

四数相加为 $0$，暴力的想法是用四个 $for$ 循环分别遍历四个数组中的每一个元素，再判断相加得到的和是否为 $0$，此时的时间复杂度高达 $O(n^4)$，因此，分组的目的就是降低时间复杂度，可以分成三种情况：

1. $Hash$ 表存一个数组 $（A）$，计算三个数组之和 $（BCD）$，时间复杂度为：$O(n)+O(n^3)=O(n^3)$
2. $Hash$ 表存三个数组之和 $（ABC）$，计算一个数组 $（D）$，时间复杂度为：$O(n^3)+O(n)=O(n^3)$
3. $Hash$ 表存两个数组之和 $（AB）$，计算两个数组之和 $（CD）$，时间复杂度为：$O(n^2)+O(n^2)=O(n^2)$

由此得到，将四个数组分为两两一组时的时间复杂度最低：$O(n^2)$

分组+哈希表

• 先遍历得到 $A，B$ 中任意两数之和的所有情况，将结果记录到哈希表中：{和：出现次数}
• 再计算 $C，D$ 中任意两数之和的 相反数 $sum$，在哈希表中查找是否存在 $key$ 为 $sum$，如果存在，则结果数加上 hash[sum]

代码实现：

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        int n = nums1.size();
        unordered_map<int, int> hash;
        for(int a: nums1){
            for(int b: nums2){
                int sum = a+b;
                ++hash[sum];
            }
        }

        int res = 0;
        for(int c: nums3){
            for(int d: nums4){
                if (hash.count(0-c-d))
                    res += hash[0-c-d];
            }
        }
        return res;
    }
};

如果需要返回对应到各个数组中的索引值，可以用一个四元组 $tuple$ 表示，若 $A[i]+B[j]+C[k]+D[l]=0$：

• 定义：vector<int, tuple<int, int, int, int>>，用于表示 {和：对应的索引元组}
• 构造：make_tuple(i, j, k, l) 得到索引的四元组
• 访问：get<index>(tuple)，表示从指定的 $tuple$ 中获得索引为 $index$ 的元素($index$ 从$0$开始)

完整代码实现：

#include <iostream>
#include <vector>
#include <tuple>
#include <unordered_map>

class Solution {
public:
    int fourSumCount(std::vector<int>& nums1, std::vector<int>& nums2, std::vector<int>& nums3, std::vector<int>& nums4) {
        int n = nums1.size();
        //A+B
        std::unordered_map<int, std::vector<std::tuple<int, int>>> hash1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int sum = nums1[i] + nums2[j];
                hash1[sum].push_back(std::make_tuple(i, j));
            }
        }
        //C+D
        std::unordered_map<int, std::vector<std::tuple<int, int>>> hash2;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int sum = nums3[i] + nums4[j];
                hash2[sum].push_back(std::make_tuple(i, j));
            }
        }

        int res = 0;
        std::vector<std::tuple<int, int, int, int>> result;  //存储结果
        for (auto iter = hash1.begin(); iter != hash1.end(); ++iter) {
            int key1 = iter->first;
            for (auto it = hash2.begin(); it != hash2.end(); ++it) {
                int key2 = it->first;
                if (key1 + key2 == 0) {
                    res += hash1[key1].size() * hash2[key2].size();
                    for (const auto& tuple1 : hash1[key1]) {
                        for (const auto& tuple2 : hash2[key2]) {
                            result.push_back(std::make_tuple(std::get<0>(tuple1), std::get<1>(tuple1),
                                std::get<0>(tuple2), std::get<1>(tuple2)));
                        }
                    }
                }
            }
        }

        std::cout << "打印可能的情况:" << std::endl;
        for (const auto& tuple : result) {
            std::cout << "(" << std::get<0>(tuple) << "," << std::get<1>(tuple)
                << "," << std::get<2>(tuple) << "," << std::get<3>(tuple) << ")" << std::endl;
        }

        return res;
    }
};

int main() {
    Solution s;
    std::vector<int> nums1 = { 1, 2 };
    std::vector<int> nums2 = { -2, -1 };
    std::vector<int> nums3 = { -1, 2 };
    std::vector<int> nums4 = { 0, 2 };
    int result = s.fourSumCount(nums1, nums2, nums3, nums4);
    std::cout << "满足条件的个数为: " << result << std::endl;
    return 0;
}

返回结果

---

 

🎇LeetCode数组中等题部分到此结束啦~希望大家做题愉快噢！🎇

如有错误，欢迎指正~！