- 移除元素
- 长度最小的子数组
- 其他
- 485. 最大连续 1 的个数">485. 最大连续 1 的个数
- 414. 第三大的数">414. 第三大的数
- 645.错误的集合">645.错误的集合
- 448. 找到所有数组中消失的数字">448. 找到所有数组中消失的数字
- 41. 缺失的第一个正数">41. 缺失的第一个正数
- 453. 最小操作次数使数组元素相等">453. 最小操作次数使数组元素相等
- 283. 移动零">283. 移动零
- 118. 杨辉三角">118. 杨辉三角
- 661. 图片平滑器">661. 图片平滑器
- 419. 甲板上的战舰">419. 甲板上的战舰
- 189. 轮转数组">189. 轮转数组
- 54. 螺旋矩阵">54. 螺旋矩阵
- 498. 对角线遍历">498. 对角线遍历
- 566. 重塑矩阵">566. 重塑矩阵
- 73. 矩阵置零">73. 矩阵置零
- 485. 最大连续 1 的个数">485. 最大连续 1 的个数
移除元素
27. 移除元素
思路：
⬇i
3 2 2 3 4 3 移除3，数组只能覆盖
⬆k
⬇ ⬇ ⬇ ⬇ ⬇
3 2 2 3 4 3 2 2 2 3 4 3 2 2 2 3 4 3 2 2 4 3 4 3 2 2 4 3 4 3
⬆ ⬆ ⬆ ⬆ ⬆
长度最小的子数组
76. 最小覆盖子串
209. 长度最小的子数组
思路：
- 暴力 O(n^3)
for i 遍历左边界
for j 遍历右边界
for i-j 求和
sum（i-j）= target ?
- 双指针
单调性
单调性：当j遍历时，j固定，若sum(i-j)>=target, i ++;
遍历的同时计算sum。
O（n）
其他
485. 最大连续 1 的个数
//双指针class Solution {public:int findMaxConsecutiveOnes(vector<int>& nums) {vector<int> s;int res = 0;//j存储当前最后一个0的下标，初始化为-1for(int i = 0, j = -1; i < nums.size(); i ++){if(nums[i] == 0) j = i;else res = max(res, i - j);}return res;}};//朴素//时间复杂度O(n),遍历一次//空间复杂度O(1)（即此算法空间复杂度为一个常量，算法执行所需要的临时空间不随着某个变量 n 的大小而变化）//变量res,max_cnt,i所需的临时空间均可复用class Solution {public:int findMaxConsecutiveOnes(vector<int>& nums) {int res = 0, max_cnt = 0;for(int i = 0; i < nums.size(); i ++){if(nums[i] == 1) res ++;else{max_cnt = max(max_cnt, res);res = 0;}}max_cnt = max(max_cnt, res);return max_cnt;}};
414. 第三大的数
- 排序
将数组从大到小排序，从头开始遍历数组，通过判断相邻元素是否不同，来统计不同元素的个数。如果能找到三个不同的元素，就返回第三大的元素，否则返回最大的元素。
时间复杂度：O(nlogn)，排序。
空间复杂度：O(log n)，排序需要的栈空间为 O(log n)。
class Solution {
public:
int thirdMax(vector<int>& nums) {
sort(nums.begin(), nums.end(), greater<>());
for(int i = 1, diff = 1; i < nums.size(); i ++)
{
if(nums[i] != nums[i - 1] && ++ diff == 3)
return nums[i];
}
return nums[0];
}
};
- set有序集合
遍历数组，同时用一个大小不超过3的有序集合来维护数组中前三大的数。
每遍历一个数，就将其插入有序集合，若有序集合的大小超过 3，就删除集合中的最小元素。
遍历结束后，若有序集合的大小为 3，其最小值就是数组中第三大的数；若有序集合的大小小于3，那么就返回有序集合中的最大值。
时间复杂度：O(n)，由于有序集合的大小至多为 3，插入和删除的时间复杂度可以视作是 O(1)
空间复杂度：O(1)
class Solution {
public:
int thirdMax(vector<int>& nums) {
set<int> s;
for(int num : nums)
{
s.insert(num);
if(s.size()>3) s.erase(s.begin());
}
//*s.rbegin():rbegin()反向迭代器指向最后一个元素，*解引用
return s.size() == 3? *s.begin() : *s.rbegin();
}
};
- 维护最大值、次大值和第三大值
时间复杂度：O(n)
空间复杂度：O(1)
class Solution {
public:
int thirdMax(vector<int> &nums) {
long a = LONG_MIN, b = LONG_MIN, c = LONG_MIN;
//LONG_MIN = -2e31
//a最大，c最小
for (long num : nums) {
if (num > a) {
c = b;
b = a;
a = num;
} else if (a > num && num > b) {
c = b;
b = num;
} else if (b > num && num > c) {
c = num;
}
}
return c == LONG_MIN ? a : c;
}
};
645.错误的集合
排序
class Solution { public: vector<int> findErrorNums(vector<int>& nums) { sort(nums.begin(),nums.end());//排序 vector<int> errornums(2);//存结果 int n = nums.size(); //处理边界 int prev = 0;//prev存储nums[i-1],初始化nums[-1] = 0 nums.push_back(n + 1);//增加nums[n] = n + 1 //一次遍历 //如果当前数等于上一个数，则当前数为重复的数；如果当前数比上一个数大2，则当前数-1为丢失的数 for(int i = 0; i <= n; i ++) { if(nums[i] == prev) errornums[0] = nums[i]; if(nums[i] - prev == 2) errornums[1] = nums[i] - 1; prev = nums[i]; } return errornums; } };时间复杂度：O(nlogn)，排序
空间复杂度：O(logn)，排序哈希表
class Solution { public: vector<int> findErrorNums(vector<int>& nums) { int n = nums.size(); vector<int> errornums(2);//存结果 //哈希表unordered_map存<num数，cnt次数> //出现两次的数为重复数 //出现一次的数为丢失数 unordered_map<int, int> num_cnt; for(int i = 0; i < n; i ++) ++num_cnt[nums[i]]; for(int num = 1; num <= n; num ++) { int cnt = num_cnt[num]; if(cnt == 2) errornums[0] = num; else if(cnt == 0) errornums[1] = num; } return errornums; } };时间复杂度：O(n)，遍历数组并填入哈希表，然后遍历从 1到 n的每个数寻找错误的集合。
空间复杂度：O(n)，需要创建大小为 O(n)的哈希表。flag标记+数学公式
flag标记：查重
数学公式：
los = (n + 1) n / 2 - (sum - rep)
los丢失的数， (n + 1) n / 2是1-n的和，sum错误集合的和，rep重复的数
class Solution {
public:
vector<int> findErrorNums(vector<int>& nums) {
const int n = nums.size();
int los = -1, rep = -1, sum = 0;
bool flag[n + 1];//1-n
memset(flag, false, sizeof(flag)); //flag标记
for(int num: nums){
sum += num; //记录总和
if(flag[num]) rep = num; //找出那个重复的元素
else flag[num] = true;
}
los = (((n + 1) * n) >> 1) - sum + rep; //数学算出丢失的元素
return vector<int>{rep, los};
}
};
时间复杂度：O(n)
空间复杂度：O(1)
- 位运算
- 异或真值表
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0
- 将错误集合每个数异或，再与1-n每个数异或，得到rep^los，rep重复的数，los丢失的数
由于b^b = 0, a^0 = 0，a ^ b ^ b = a，异或同一个数偶数次会将这个数字消去；
2. lowbit求出rep ^ los 中的最后（右）一位1，rep，los在该位必定为一个1，一个0
记rep ^ los = i，lowbit = -i& i
然后找出错误集合里所有该位置是0的数字异或在一起，在于1 ~ n中所有该位置是0的数字异或在一起，可得出rep和los的其中之一，在于rep ^ los异或，可得出另一个数字；
3. 最后遍历一遍数组，确定哪个数字是rep，另一个数字是los。
class Solution {
public:
vector<int> findErrorNums(vector<int>& nums) {
const int n = nums.size();
int sum = 0;
for(int i = 0; i < n; ++i) sum ^= (i + 1) ^ nums[i]; //异或原数组和1 ~ n
int lowbit = sum & (-sum); //找出最低位的1，这个1只能由rep和los中的一个提供
int num1 = 0;
for(int i = 0; i < n; ++i){
if(((i + 1) & lowbit) == 0) num1 ^= (i + 1); //如果最低位是0，异或入num1
if((nums[i] & lowbit) == 0) num1 ^= nums[i];
}
for(int num : nums) if (num == num1) return vector<int>{num1, sum ^ num1};
return vector<int>{sum ^ num1, num1};
}
};
448. 找到所有数组中消失的数字
- set
时间复杂度：O(n)
空间复杂度：O(n)
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
const int n = nums.size();
vector<int> ans;
unordered_set<int> s;
for(int i = 0; i < n; i ++) s.insert(nums[i]);
for(int i = 1; i <= n; i ++)
if(s.count(i) == 0) ans.push_back(i);
return ans;
}
};
- 数组的原地操作
时间复杂度：O(n)
空间复杂度：O(1)
当前元素是 nums[i]，把第 abs(nums[i]) - 1位置的元素乘 -1，表示这个该位置出现过。如果第 abs(nums[i]) - 1位置的元素已经是负数了，表示 nums[i]已经出现过了，就不用再把第 nums[i] - 1位置的元素乘以 -1。最后，对数组中的每个位置遍历一遍，如果 i位置的数字是正数，说明 i未出现过。
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
const int n = nums.size();
vector<int> ans;
for(int i = 0; i < n; i ++)
if(nums[abs(nums[i]) - 1] > 0) nums[abs(nums[i]) - 1] *= -1;
for(int i = 0; i < n; i ++)
if(nums[i] > 0) ans.push_back(i + 1);
return ans;
}
};
41. 缺失的第一个正数
/*
x属于[1,n]，将x映射到nums[x - 1]
具体来说，遍历数组，当前数x=nums[i]，满足条件时，将x与nums[x - 1]交换
（1）大于等于1，小于等于n；
（2）判断应该映射到的点nums[x - 1]上是否已被重复的数映射（等同于数值等于下标+1）
整理数组后，最后遍历数组，如果某个数不等于下标＋1，则这个数就是缺失的第一个正数；
如果找不到这样的数，则n+1为缺失的第一个整数
*/
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
for(int i = 0; i < n; i ++)
{
while(nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i])
swap(nums[i], nums[nums[i] - 1]);
}
for(int i = 0; i < n; i ++)
if(nums[i] != i + 1)
return i + 1;
return n + 1;
}
};
时间复杂度：
第一次遍历O（n），其中while循环不会在每一层for循环内把数组里面的所有元素都看一遍。如果有一些元素在这一次的循环中被交换到了它们应该在的位置，那么在后续的遍历中，由于它们已经在正确的位置上了，代码再执行到它们的时候，就会被跳过。
极端情况：在第 1 个位置经过这个 while 就把所有的元素都看了一遍，这个所有的元素都被放置在它们应该在的位置，那么 for 循环后面的部分的 while 的循环体都不会被执行。
平均下来，每个数只需要看一次就可以了，while 循环体被执行很多次的情况不会每次都发生。均摊复杂度分析
最后再遍历了一次数组，最坏情况下要把数组里的所有的数都看一遍，因此时间复杂度是 O(n)。
453. 最小操作次数使数组元素相等
/*
选出n-1个增加1 等价于 剩下那个减少1
1. 遍历一遍所有元素，找到最小的元素。
2. 再遍历一遍，累加所有元素和最小元素的差距，差距之和则为最小操作数。
差距之和通过再次遍历，求每个数和最小值之差得到。
*/
class Solution {
public:
int minMoves(vector<int>& nums) {
int n = nums.size();
int min_x = nums[0];
int res = 0;
for(int i = 0; i < n; i ++)
min_x = min(min_x, nums[i]);
for(int i = 0; i < n; i ++)
res += nums[i] - min_x;
return res;
}
};
283. 移动零
/*
双指针
i指向非0数，j指向当前数组的第一个0；
nums[j] = nums[i]; nums[i] = 0;
j何时+1？
1.当j = i，且指向非0数时，j++
2.当j < i，且nums[j] = nums[i]; nums[i] = 0;后，j++
*/
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int n = nums.size();
for(int i = 0, j = 0; i < n; i ++)
{
if(nums[i] != 0)//i指向非0数
{
if(j < i)
{
nums[j] = nums[i];
nums[i] = 0;
}
j ++;//当j < i 和 j = i时，j都要＋1
}
}
}
};
118. 杨辉三角
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> y_tri(numRows);
for(int i = 0; i < numRows; i ++)
{
//将第i行的vector大小设置为i+1
y_tri[i].resize(i + 1);
y_tri[i][0] = y_tri[i][i] = 1;
for(int j = 1; j < i; j ++)//从每一行第二个数j=1开始,若从j=0开始，j-1会溢出
y_tri[i][j] = y_tri[i - 1][j - 1] + y_tri[i - 1][j];
}
return y_tri;
}
};
661. 图片平滑器
/*
将所有邻居的和保存在 res[i][j] 中，同时记录邻居的数目count。最终的答案就是和除以邻居数目。
*/
class Solution {
public:
vector<vector<int>> imageSmoother(vector<vector<int>>& img) {
int r = img.size();
int c = img[0].size();
vector<vector<int>> res(r, vector<int>(c));
for(int i = 0; i < r; i ++)
{
for(int j = 0; j < c; j ++)
{
int count = 0;
for(int nr = i - 1; nr <= i + 1; nr ++)
{
for(int nc = j - 1; nc <= j + 1; nc ++)
{
if(nr >= 0 && nr < r && nc >= 0 && nc < c)
{
count ++;
res[i][j] += img[nr][nc];
}
}
}
res[i][j] = res[i][j] / count;
}
}
return res;
}
};
419. 甲板上的战舰
/*
碰到作为战舰头的X，数量加一
如果当前X，左边或者上面有X，则当前X不是战舰头
*/
class Solution {
public:
int countBattleships(vector<vector<char>>& board) {
int m = board.size(), n = board[0].size();
int cnt = 0;
for(int i = 0; i < m; i ++)
for(int j = 0; j < n; j ++)
{
if(board[i][j] == 'X')
{
if((i >= 1 && board[i - 1][j] == 'X') || (j >= 1 && board[i][j - 1] == 'X')) continue;
cnt ++;
}
}
return cnt;
}
};
189. 轮转数组
- 使用额外的数组
时间复杂度O(n)
空间复杂度O(n)
/*
利用额外的数组newarr存储
newarr[(i + k) % n] = nums[i];
*/
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
vector<int> newarr(n);
for(int i = 0; i < n; i ++)
newarr[(i + k) % n] = nums[i];
//assign实现顺序容器的赋值
nums.assign(newarr.begin(), newarr.end());
}
};
- 数组翻转
时间复杂度O(n)
空间复杂度O(1)
class Solution {
public:
void reverse(vector<int>& nums, int start, int end)
{
while(start < end)
{
swap(nums[start], nums[end]);
start ++;
end --;
}
}
void rotate(vector<int>& nums, int k) {
int n = nums.size();
k = k % n;//处理k > n的情况
reverse(nums, 0, n - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, n - 1);
}
};
- 环状替换
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size(), cnt = n;
int pos = 0, temp = nums[0], pre = nums[0];
int st = 0;//st存储每个环起点
if(k % n == 0) return;//k是n的倍数时，数组不变
while(cnt-- != 0)//循环n次，覆盖n次
{
pos = (pos + k) % n;
temp = nums[pos];
nums[pos] = pre;
pre = temp;
if(pos == st)//回到原点
{
pos = ++ st;//st先加1，再赋值给pos
temp = nums[pos];
pre = nums[pos];
}
}
}
};
54. 螺旋矩阵
- 方法一 存储路径+改变方向
题解
时间复杂度：O(mn)，矩阵中的每个元素都要被访问一次。
空间复杂度：O(mn)。需要创建一个大小为 m×n 的矩阵visited 记录每个位置是否被访问过。
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int rows = matrix.size(), cols = matrix[0].size();//输入rows*cols
int total = rows * cols;
vector<int> order;//存储路径
vector<vector<bool>> visited(rows, vector<bool>(cols));//visited存储路径里是否有该点，默认fault
int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};//顺时针优先顺序：向右，向下，向左，向上
if(rows == 0 || cols == 0) return {};
int direidx = 0;//默认方向向右
int row = 0, col = 0;
while(order.size() < total)//order路径里包含total个点即循环结束
{
order.push_back(matrix[row][col]);
visited[row][col] = true;
//更新row，col
//保持原方向,得到[nextrow][nextcol],如果该点超出边界或者已经在路径中，则顺时针改变方向
int nextrow = row + directions[direidx][0], nextcol = col + directions[direidx][1];
if(nextrow < 0 || nextrow >= rows || nextcol < 0 || nextcol >= cols || visited[nextrow][nextcol])
direidx = (direidx + 1) % 4;
row += directions[direidx][0], col += directions[direidx][1];
}
return order;
}
};
- 判断每一层的上下左右边界
题解
时间复杂度：O（mn）
空间复杂度：O(1)，除了输出数组以外，空间复杂度是常数。
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int rows = matrix.size(), cols = matrix[0].size();//输入rows*cols
vector<int> order;//存储路径
if(matrix.empty()) return{};
//初始化上下左右边界
int u = 0, d = rows - 1, l = 0, r = cols - 1;
while(1)
{
//向右
for(int i = l; i <= r; i ++) order.push_back(matrix[u][i]);
u ++;
if(u > d) break;//上边界++，如果超过下边界，结束循环
//向下
for(int i = u; i <= d; i ++) order.push_back(matrix[i][r]);
r --;
if(r < l) break;//右边界--，如果超过左边界，结束循环
//向左
for(int i = r; i >= l; i --) order.push_back(matrix[d][i]);
d --;
if(d < u) break;//下边界--，如果超过上边界，结束循环
//向上
for(int i = d; i >= u; i --) order.push_back(matrix[i][l]);
l ++;
if(l > r) break;//左边界++，如果超过右边界，结束循环
}
return order;
}
};
498. 对角线遍历
题解
时间复杂度：O（mn）
空间复杂度：O（1）
/*
第i条对角线(从左上开始)上的点，其坐标(x,y)，满足x + y = i，共row+cols-1条对角线
第0，2，4...条对角线，x起始值 x = (i < rows) ? i : rows - 1; y起始值 i - x
x减1，y加1；最终x等于0，或者y等于cols-1
第1，3，5...条对角线，y起始值 y = (i < cols) ? i : cols - 1; x起始值 i - y
y减1，x加1；最终y等于0，或者x等于rows-1
*/
class Solution {
public:
vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
int rows = mat.size(), cols = mat[0].size();
vector<int> res;
bool evendiag = true;
for(int i = 0; i < rows + cols; i ++)//i表示对角线上x+y
{
int len = evendiag ? rows : cols;
int border = evendiag ? cols : rows;
int x = i < len ? i : len - 1;
int y = i - x;
while(x >= 0 && y <= border - 1)
{
//evendiag = false时，x表示纵坐标，x表示横坐标，需反过来
res.push_back(evendiag ? mat[x][y] : mat[y][x]);
x --;
y ++;
}
evendiag = !evendiag;
}
return res;
}
};
566. 重塑矩阵
//一维数组中的第i个数转化为m*n二维数组中的[i / n][i % n]
//m*n -> 一维 -> r*c
class Solution {
public:
vector<vector<int>> matrixReshape(vector<vector<int>>& mat, int r, int c) {
vector<vector<int>> res(r, vector<int>(c));
int m = mat.size(), n = mat[0].size();
if(r * c != m * n) return mat;
int cnt = 0;
for(int i = 0; i < m * n; i ++)
res[i / c][i % c] = mat[i / n][i % n];
return res;
}
};
73. 矩阵置零
- 额外一行一列数组标记
空间复杂度O(m+n)
时间复杂度O(mn)
题解
/*
先遍历一次，如果点[i][j]为0，则标记行数组和列数组分别存储i,和j；
再遍历一次，如果点[i][j],i在行数组中或j在列数组中，则将点置零
*/
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
vector<bool> row(m), col(n);
for(int i = 0; i < m; i ++)
for(int j = 0; j < n; j ++)
if(matrix[i][j] == 0)
{
row[i] = true;
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;
}
};
- 用首行首列标记
空间复杂度O(1)
时间复杂度O(mn)
题解
/*
*/
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
bool flag_r0 = false, flag_c0 = false;
//检查第一行是否有0，是则标记为真
for(int i = 0; i < n; i ++)
if(matrix[0][i] == 0)
{
flag_r0 = true;
break;
}
//检查第一列是否有0，是则标记为真
for(int i = 0; i < m; i ++)
if(matrix[i][0] == 0)
{
flag_c0 = true;
break;
}
//遍历非首行首列，如果该点为0，则对应的首行首列元素置零标记
for(int i = 1; i < m; i ++)
for(int j = 1; j < n; j ++)
{
if(matrix[i][j] == 0)
{
matrix[0][j] = 0;
matrix[i][0] = 0;
}
}
//非首行首列元素置零
for(int i = 1; i < m; i ++)
for(int j = 1; j < n; j ++)
if(matrix[0][j] == 0 || matrix[i][0] == 0)
matrix[i][j] = 0;
//如果第一行有0，将第一行置零
for(int i = 0; i < n; i ++)
if(flag_r0) matrix[0][i] =0;
//如果第一列有0，将第一列置零
for(int i = 0; i < m; i ++)
if(flag_c0) matrix[i][0] =0;
}
};
若有收获，就点个赞吧
0 人点赞
