1.leetcode-35. 搜索插入位置（简单）
（1）题目描述
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
（2）方法及思路（二分查找）
考虑这个插入的位置 pos，它成立的条件为：
nums[pos−1]<target≤nums[pos] ；
问题转化到这里，直接套用二分法即可，即不断用二分法逼近查找第一个大于等于 target的下标 。
（3）代码实现
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）题目描述
给你一个满足下述两条属性的 m x n 整数矩阵：
每行中的整数从左到右按非递减顺序排列。
每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
（2）思路与方法（二分查找）
1.首先先把此二维数组看作是一个一维数组的变形。
2.若将矩阵每一行拼接在上一行的末尾，则会得到一个升序数组，我们可以在该数组上二分找到目标元素。
3.代码实现时，可以二分升序数组的下标，将其映射到原矩阵的行和列上。
（3）代码实现
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的下标）
3.leetcode-73. 矩阵置零（中等）
（1）题目描述
给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
（2）方法及思路（使用标记数组）
1.先定义两个一维数组，分别代表行和列
2.遍历一遍数组，找出0元素所在的行和列，并在已定义的数组中用true赋值标记出来。
3.再次遍历数组，当遍历到被标记的行或列时，就将其值改为0。
（3）代码实现
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. 合并区间（中等）
（1）题目描述
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
（2）方法及思路（排序）
思路：
如果我们按照区间的左端点排序，那么在排完序的列表中，可以合并的区间一定是连续的。如下图所示，标记为蓝色、黄色和绿色的区间分别可以合并成一个大区间，它们在排完序的列表中是连续的：
算法：
1.我们用数组 merged 存储最终的答案。
2.首先，我们将列表中的区间按照左端点升序排序。然后我们将第一个区间加入 merged 数组中，并按顺序依次考虑之后的每个区间：
3.如果当前区间的左端点在数组 merged 中最后一个区间的右端点之后，那么它们不会重合，我们可以直接将这个区间加入数组 merged 的末尾；
4.否则，它们重合，我们需要用当前区间的右端点更新数组 merged 中最后一个区间的右端点，将其置为二者的较大值。
（3）代码实现
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. 螺旋矩阵（中等）
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
（2）方法及思路（模拟）
可以模仿上一篇文章中的螺旋寻找
函数接受一个二维数组matrix作为参数，并返回一个一维数组ans。函数首先获取二维数组的行数和列数，然后使用top、bottom、left和right来表示当前螺旋循环的边界。count表示剩余要输出的元素个数。
在循环中，首先从左到右输出上边界的元素，每输出一个元素，count减1并将其添加到ans中。然后将top加1，表示上边界收缩。接下来从上到下输出右边界的元素，并更新右边界。之后从右到左输出下边界的元素，更新下边界。最后从下到上输出左边界的元素，更新左边界。每次循环结束时，检查count是否大于等于1，如果是则继续循环，否则退出循环。
最后返回ans。
（3）代码实现文章来源：https://www.toymoban.com/news/detail-686571.html
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. 两数之和（简单）
（1）题目描述
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
（2）方法及思路（双指针）
先在头上定义一个指针，在其后面也定义一个指针，然后循环找出符合要求的数。
（3）代码实现文章来源地址https://www.toymoban.com/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;
}
};
到了这里，关于【算法刷题之数组篇（2）】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
