剑指 offer 数组题目汇总（C++版）
 

1、数组中重复的数字
一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。找出数组中任意一个重复的数字。
思路1：先排序，在遍历。 时间复杂度：O(nlog(n)) ，空间复杂度：O(1)
思路2：遍历数组时查询哈希表是否已有这个数，有就返回，没有就添加。时间复杂度：O(n)， 空间复杂度：O(n)

思路1和2比较简单，代码就不贴了。主要说一下下面的方法。
思路3：原地哈希，注意题目条件，长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内，可以用 swap() 函数使 numbers 里面的数对应到数组的下标上。
时间复杂度：O(n)， 空间复杂度：O(1)

遍历整个数组：
1、当 numbers[i] 等于下标 i，判断下一个下标是否对应；
2、当 numbers[i] 不等于下标 i，分两种情况
(1)numbers[i]==numbers[numbers[i]]，此时对应下标i的 numbers[i] 已对应，出现重复数字，返回该数；
(2)否则 swap(numbers[numbers[i]],numbers[i])；
3、遍历结束都未发现重复数字，则返回-1；

int findRepeatNumber(vector<int>& nums) {
        if(!nums.size()) return -1;
        for(int i = 0;i < nums.size();) {
            if(i == nums[i]) i++;
            else if(nums[i] == nums[nums[i]]) return nums[i];
            else swap(nums[i],nums[nums[i]]);
        }
        return -1;
    }

2、二维数组中的查找
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。完成一个高效的函数，输入这样的二维数组和一个整数，判断数组中是否含有该整数。
数组长这样：

思路：利用这个数组的性质，我们从左下角那个数开始遍历数组，维护二维数组遍历到的行下标 i 和列下标 j，如果当前遍历到的数与目标相等直接返回true，如果当前遍历到的数大于目标值，那么令 i 减一，否则 j 加一。
时间复杂度：O(n)， 空间复杂度：O(1)

bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        if(matrix.empty() || matrix[0].empty()) return false;
        int row = matrix.size(),column = matrix[0].size(),i = row-1,j = 0;
        while(i>=0 && j < column) {
            if(matrix[i][j] == target) return true;
            else if(matrix[i][j] > target) i--;
            else j++;
        }
        return false;
    }

3、旋转数组中的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，称为数组的旋转。输入一个递增排序数组的一个旋转，输出旋转数组的最小元素。如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。
思路1：排序之后取第一个数，时间复杂度O(nlog(n)) ，空间复杂度：O(1)
思路2：二分查找法，这里我们把目标 target 看作是右端点来分析，分以下三种情况。

情况1，arr[mid] > target：4 5 6 1 2 3
arr[mid] 为 6， target为右端点 3， arr[mid] > target，说明[l… mid] 都是 >= target 的，因为原始数组是非递减，所以可以确定答案为 [mid+1…r]区间，所以 l = mid + 1

情况2，arr[mid] < target：5 6 1 2 3 4
arr[mid] 为 1， target为右端点 4， arr[mid] < target, 说明答案肯定不在[mid+1…r]，但是arr[mid] 有可能是答案，所以答案在[l, mid]区间，所以r = mid

情况3，arr[mid] == target：
如果是 1 0 1 1 1， arr[mid] = target = 1, 显然答案在左边
如果是 1 1 1 0 1, arr[mid] = target = 1, 显然答案在右边
所以这种情况，不能确定答案在左边还是右边，那么让r = r - 1，慢慢缩减区间。
最坏时间复杂度O(n)，一般情况是O(log(n))

int minArray(vector<int>& numbers) {
        if(!numbers.size()) return -1;
        int l = 0,r = numbers.size()-1;
        while(l<r) {
            int mid = l+r >> 1;
            if(numbers[mid] > numbers[r]) l = mid+1;
            else if(numbers[mid] < numbers[r]) r = mid;
            else r--;
        }
        return numbers[l];
    }

4、调整数组顺序使奇数位于偶数前面
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。对奇数和偶数的相对位置没有要求。
思路1：新开两个vector，遍历原数组，将奇数存在一个vector里，偶数存在另一个vector里，然后遍历存偶数那个vector把里面的数在存到奇数那个vector里。
时间复杂度O(n) ， 空间复杂度O(n)
这个方法代码较简单且不是最好的方法，代码就不帖了。
思路2：双指针算法，定义头尾两个指针，向中间开始遍历，如果头指针遇到奇数则其下标加一，同样尾指针遇到偶数下标减一，否则需要交换两个指针指向的数且头尾指针各自向中间移动一位。
时间复杂度O(n) ，空间复杂度O(1)

vector<int> exchange(vector<int>& nums) {
        if(!nums.size()) return nums;
        int l = 0,r = nums.size()-1;
        while(l<r) {
            if(nums[l]%2 == 1) l++;
            else if(nums[r]%2 == 0) r--;
            else {
                swap(nums[l++],nums[r--]);
            }
        }
        return nums;
    }

思考：如果题目要求保证奇数和奇数、偶数和偶数的相对顺序呢？

5、数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。假设数组是非空的且给定的数组总是存在多数元素。
思路1：先排序，然后取中间的数
时间复杂度O(nlog(n)) ，空间复杂度O(1)

思路2：空间换时间，使用哈希表记录数字的出现次数
时间复杂度O(n) ，空间复杂度O(n)

int majorityElement(vector<int>& nums) {
        if(!nums.size()) return -1;
        unordered_map<int,int> hash;
        for(auto t:nums) {
            hash[t]++;
            if(hash[t] > nums.size()/2) return t;
        }
        return -1;
    }

6、最小的k个数
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
思路1：先排序，再取前k个数返回即可
时间复杂度O(nlog(n)) ，空间复杂度O(1)

思路2：使用大顶堆，遍历数组，如果堆大小小于k，那就向堆里添加数，否则判断堆顶如果大于当前遍历到的数，那么将堆顶弹出，将该数入堆，使得堆里面始终维护最小的k个数
时间复杂度O(nlog(k)) ，空间复杂度O(k)

vector<int> getLeastNumbers(vector<int>& arr, int k) {
        vector<int> res;
        if(!arr.size() || k > arr.size()) return res;
        
        priority_queue<int> heap;
        for(auto t:arr) {
            if(heap.size() < k) heap.push(t);
            else if(heap.size() && heap.top() > t) {
                heap.pop();
                heap.push(t);
            }
        }
        
        while(heap.size()) {
            res.push_back(heap.top());
            heap.pop();
        }
        
        return res;
    }

7、连续子数组的最大和
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)
举例：
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
思路：定义两个变量 res 和 curSum，其中 res 保存最终的最大的子数组之和，curSum 初始值为 0，每遍历一个数字 t，比较 curSum + t 和 t 中的较大值存入 curSum，然后将 res 和 curSum 中的较大值存入 res，以此类推直到遍历完整个数组

int maxSubArray(vector<int>& nums) {
        if(!nums.size()) return 0;
        int curSum = 0, res = nums[0];
        for(auto t:nums) {
            curSum = max(curSum + t, t);
            res = max(res, curSum);
        }
        return res;
    }

8、在排序数组中查找数字
统计一个数字在排序数组中出现的次数。
举例：
输入: nums = [5,7,7,8,8,10]， target = 8
输出: 2
直接遍历也行（那么今天的面试可能就到这了emmm），面试时明显是想考你二分法，下面说下二分解法
建议先看一下牛批的二分法模板，传送门：二分查找算法模板（太强了兄die！）

思路：数组有序，两次二分，第一次二分查找第一个 >= target 的位置 l；第二次二分查找最后一个 <= target 的位置 r，查找成功则返回 end - begin + 1，即为数字在排序数组中出现的次数，否则返回0，表示该数没有在数组中出现
时间复杂度O(log(n)) ，空间复杂度O(1)

int search(vector<int>& nums, int target) {
        if(!nums.size()) return 0;
        int l = search1(nums,target),r = search2(nums,target);
        if(nums[l] != target || nums[r] != target) return 0;
        return r-l+1;
    }

    int search1(vector<int>& nums, int target) {
        int l = 0,r = nums.size()-1, ans = 0;
        while(l<r) {
            int mid = l+r >> 1;
            if(nums[mid] >= target) r = mid;
            else l = mid+1;
        }
        return r;
    }
    int search2(vector<int>& nums, int target) {
        int l = 0,r = nums.size()-1;
        while(l<r) {
            int mid = (l+r+1) >> 1;
            if(nums[mid] <= target) l = mid;
            else r = mid-1;
        }
        return r;
    }

9、0~n-1中缺失的数字
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
举例：
输入: [0,1,3]
输出: 2

输入: [0,1,2,3,4,5,6,7,9]
输出: 8

思路：对于有序数组, 一般会想到二分查找算法，大小为 i 的数应当处于下标为 i 的位置上，如果不在， 说明在该数字发生了错位，我们可以利用 nums[i] 是否等于mid 划分数组为两部分
时间复杂度O(log(n)) ，空间复杂度O(1)

int missingNumber(vector<int>& nums) {
        if(!nums.size()) return -1;
        int l = 0,r = nums.size()-1;
        while(l<r) {
            int mid = l+r >> 1;
            if(nums[mid] != mid) r = mid;
            else l = mid+1;
        }
        // 如果从0 ~ n - 1都不缺值, 则缺少的是n
        return (l == nums.size() - 1 && nums[l] == l) ? l + 1 : l;
    }

10、数组中出现数字其一
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
思路1：如果没有空间复杂度的要求，那么可以用哈希表存储每个数的出现次数，然后返回出现次数为1的数。
思路2：位运算
1.总体思路：有一道和它类似的题，求数组中只有一个出现一次的数，解法就是从头开始不断地异或，由于相同的两个数异或值为0，因此最终的异或结果就是答案
2.而本题有两个只出现一次的数a和b按异或方法最终只能得到a异或b的值，就需要思考一下这两个数异或的结果有何特点
3.可以发现，首先这两个数一定不同，故异或结果一定不为0，那么a异或b的结果中一定有一位为1，假设是第x位，那么就说明了a和b的二进制的第x位不同，根据这一特点,我们可以将数组分为两个集合，即第x位为1的数的集合和第x位为0的数的集合，这两部分分别异或出来的两个值就是a和b的值
4.要求二进制的最后一位1，可以用lowbit运算，它可以快速得到x的最后一位的1
时间复杂度：O(n) 空间复杂度：O(1)

vector<int> singleNumbers(vector<int>& nums) {
        if(!nums.size()) return nums;
        int s = 0;//s是要找的两个数的异或结果
        for(auto t:nums) s ^= t;
        int flag = lowBit(s);
        int a = 0,b; //a和b是要求的两个数
        //根据flag对所有数分组，a一定是要找的数之一
        for(auto t:nums) {
            if(flag & t) a ^= t;
        }
        b = s ^ a;
        vector<int> res{a,b};
        return res;
    }

    //取x最低位的1（二进制为0000 0011，最低为1的那一位是第1位，所以取出后为0000 0001）
    int lowBit(int x) {
        return x & -x;
    }

11、数组中出现的数字其二
一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。找出只出现一次的数字。
思路1：可以用哈希表存储每个数的出现次数，然后返回出现次数为1的数。
时间复杂度：O(n) 空间复杂度：O(n)
思路2：采用位运算，考虑数字的二进制形式，对于出现三次的数字，各 二进制位 1 出现的次数都是 3 的倍数。因此，统计所有数字的各二进制位中 1 的出现次数，并对 3 求余，结果则为只出现一次的数字。
时间复杂度：O(n) 空间复杂度：O(1)

int singleNumber(vector<int>& nums) {
        if(!nums.size()) return 0;
        int res = 0;
        //建立一个 32 位的数字来统计每一位上1出现的个数
        for(int i = 0;i < 32;i++) {
            int sum = 0;
            //统计所有数二进制位最右边的1的个数
            for(int j = 0;j < nums.size();j++) {
                sum += (nums[j]>>i) & 1;
            }
            res |= (sum%3) << i; //计算每个二进制位对结果的贡献
        }
        return res;
    }

12、和为s的两个数
输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
思路1：使用哈希表通过遍历一遍数组来找到数字的组合。
时间复杂度：O(n) 空间复杂度：O(n)
思路2：因为数组是升序的，可以利用其性质使用双指针算法。定义头尾两个指针，如果指向的这两个数相加正好是目标值，那返回这两个数，如果相加小于目标值那么使头指针加一，否则尾指针减一
时间复杂度：O(n) 空间复杂度：O(1)

vector<int> twoSum(vector<int>& nums, int target) {
        if(!nums.size()) return {};
        int l = 0,r = nums.size()-1;
        while(l<r) {
            if(nums[l] + nums[r] == target) return vector<int> {nums[l], nums[r]};
            else if(nums[l] + nums[r] < target) l++;
            else r--;
        }
        return {};
    }

13、顺时针打印矩阵
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
举例：

思路1：可以定义上下左右四个边界， 并按照 “从左向右、从上向下、从右向左、从下向上” 四个方向循环，每个方向打印过程中做以下三件事 （各方向的具体信息见下表） ；
（1）根据边界打印，即将元素按顺序添加至列表 res 尾部；
（2）边界向内收缩 11 （代表已被打印）；
（3）判断是否打印完毕（边界是否相遇），若打印完毕则跳出。

时间复杂度：O(mn) 空间复杂度：O(1)

vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> res;
        if(!matrix.size()) return {};
        int l = 0,r = matrix[0].size()-1,t = 0,b = matrix.size()-1;//定义左右上下边界
        while(true) {
            //左到右
            for(int i = l;i <= r;i++) res.push_back(matrix[t][i]);
            if(++t > b) break;
            //上到下
            for(int i = t;i <= b;i++) res.push_back(matrix[i][r]);
            if(--r < l) break;
            //右到左
            for(int i = r;i >= l;i--) res.push_back(matrix[b][i]);
            if(--b < t) break;
            //下到上
            for(int i = b;i >= t;i--) res.push_back(matrix[i][l]);
            if(++l > r) break;
        }
        return res;
    }

思路2：上面代码可能有些不太优雅，因为有四个 for 循环，还可以使用另一种方法，需要消耗一定空间保存一下哪些点已经被访问了。
时间复杂度：O(mn) 空间复杂度：O(mn)

vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> res;
        if(!matrix.size()) return res;
        int row = matrix.size(),col = matrix[0].size();
        vector<vector<bool>> flag(row, vector<bool>(col,false));
        int dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1}; //定义x轴和y轴四个方向 上右下左（顺时针）
        int x = 0,y = 0, d = 1; //变量d是负责转弯用的

        for(int k = 0;k < row*col;k++) {  //遍历所有点
            res.push_back(matrix[x][y]);
            flag[x][y] = true;  //已经遍历过的打上标记

            int a = x + dx[d], b = y + dy[d]; //下一个要遍历的点的可能位置
            if(a<0 || a>=row || b<0 || b >= col || flag[a][b]) { //如果这个点的位置不符合规定 需要转弯
                d = (d+1) % 4;  //转弯
                a = x + dx[d],b = y + dy[d]; //新点的位置
            }

            x = a, y = b;  下一个要遍历的点的准确位置
        }
        
        return res;
    }

思考：如果要逆时针打印矩阵呢，该如何修改上述两种方法的代码？

14、矩阵中的路径
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
举例：
下面的 3×4 的矩阵中可以包含单词 “ABCCED”

思路：深度优先遍历 DFS，原二维数组像一个迷宫，可以上下左右四个方向行走，我们以二维数组中每一个数都作为起点和给定字符串做匹配，过程中需要将已经使用过的字母改成一个特殊字母，以避免重复使用字符（也可以定义一个和原数组等大的 visited 数组用来记录当前位置是否已被访问过）。如果二维数组 board 的当前字符和目标字符串 word 对应的字符相等，则对其上下左右四个邻字符分别调用 DFS 的递归函数，只要有一个返回 true，那么就表示可以找到匹配的字符，否则就不能找到
时间复杂度分析：单词起点一共有 m ∗ n mnm∗n 个，单词的每个字母一共有上下左右四个方向可以选择，但由于不能走回头路，所以除了单词首字母外，仅有三种选择。所以总时间复杂度是 O(m n ∗ 3 k mn3^kmn∗3k)。

bool exist(vector<vector<char>>& board, string word) {
        if(!board.size()) return false;
        for(int i = 0;i < board.size();i++) {
            for(int j = 0;j < board[0].size();j++) {
                if(dfs(board,word,0,i,j)) return true;
            }
        }
        return false;
    }

    bool dfs(vector<vector<char>>& board,string &word,int u,int x,int y) {
        if(board[x][y] != word[u]) return false; //当前字符不匹配直接返回false
        if(u == word.size()-1) return true; //当前字符已经匹配完了字符串的最后一个字符
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; //定义四个方向
        char t = board[x][y];
        board[x][y] = '*';  //当前字符修改为*号，以避免重复使用字符
        //向四个邻字符分别调用递归函数，只要有一个返回 true，那么就表示可以找到匹配的字符
        for (int i = 0; i < 4; i ++ ) { 
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < board.size() && b >= 0 && b < board[a].size()) {
                if (dfs(board, word, u + 1, a, b)) return true;
            }
        }
        board[x][y] = t; //递归调用完后需恢复之前的状态
        return false;
    }

15、机器人的运动范围
地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

思路：从 (0, 0) 点开始，每次朝上下左右四个方向扩展新的节点即可。扩展时需要注意新的节点需要满足如下条件：

之前没有遍历过，可以用个 bool 数组判断；
没有走出边界；
横纵坐标的各位数字之和小于 k；

最后答案就是所有遍历过的合法的节点个数。

时间复杂度分析：因为有 bool 数组判重，每个点只会搜索一遍，一共只有 O(nm) 个格子，所以总时间复杂度是 O(nm)。

class Solution {
public:
    int movingCount(int m, int n, int k) {
        vector<vector<bool>> flag(m,vector<bool>(n,false));
        int res = dfs(0,0,k,flag);
        return res;
    }

    int dfs(int x, int y, int k,vector<vector<bool>> &flag) {
        int sum = getSum(x,y);//获取坐标数位之和
        //边界条件判定
        if(x<0 || x>=flag.size() || y<0 || y>=flag[0].size() || flag[x][y] || sum>k) return 0;
        flag[x][y] = true; //标记该位置已经走过
        return dfs(x+1,y,k,flag) + dfs(x-1,y,k,flag) + dfs(x,y+1,k,flag) + dfs(x,y-1,k,flag) + 1;
    }

    int getSum(int x,int y) {
        int sum = 0;
        while(x) {
            sum += x%10;
            x /= 10;
        }
        while(y) {
            sum += y%10;
            y /= 10;
        }
        return sum;
    }
};