🌈个人主页：聆风吟
🔥系列专栏：数据结构、剑指offer每日一练
🔖少年有梦不应止于心动，更要付诸行动。
一. ⛳️寻找文件副本(题目难度：简单)
⌈ 在线OJ链接,可以转至此处自行练习 ⌋
1.1 题目
设备中存有 n 个文件，文件 id 记于数组 documents。若文件 id 相同，则定义为该文件存在副本。请返回任一存在副本的文件 id。
1.2 示例
输入： documents = [2, 5, 3, 0, 5, 0]
输出： 0 或 5
1.3 限制
- 0 ≤ documents[i] ≤ n-1
- 2 <= n <= 100000
1.4 解题思路一
排序+遍历
对数组首先进行排序，然后遍历数组，如果documents[i] = documents[i+1]，则返回doucuments[i]即可。
c++代码
class Solution {
public:
int findRepeatDocument(vector<int>& documents) {
//对数组进行排序
sort(documents.begin(),documents.end());
//遍历查找，判断documents[i]是否等于documents[i+1]
for(int i=0;i<documents.size()-1;i++)
{
if(documents[i]==documents[i+1]) return documents[i];
}
//如果不存在，返回-1
return -1;
}
};
1.5 解题思路二
哈希表
利用数据结构特点，容易想到使用哈希表记录数组的各个数字，当查找到重复数字则直接返回。
- 初始化： 新建 HashSet ，记为 map ；
- 遍历数组 documents 中的每个数字 doc：
- 如果doc在hmap中，说名重复，直接返回doc;
- 如果不在，将doc添加至hmap中；
- 如果不存在，返回-1。
c++代码
class Solution {
public:
int findRepeatDocument(vector<int>& documents) {
//新建 HashSet ，记为 map
unordered_map<int, bool> map;
//遍历数组 documents 中的每个数字 doc
// 1. 如果doc在hmap中，说名重复，直接返回doc;
// 2. 如果不在，将doc添加至hmap中；
for(int doc : documents) {
if(map[doc]) return doc;
map[doc] = true;
}
//如果不存在，返回-1
return -1;
}
};
二. ⛳️螺旋遍历二维数组(题目难度：简单)
⌈ 在线OJ链接,可以转至此处自行练习 ⌋
1.1 题目
给定一个二维数组 array，请返回「螺旋遍历」该数组的结果。
螺旋遍历： 从左上角开始，按照 向右、向下、向左、向上 的顺序 依次 提取元素，然后再进入内部一层重复相同的步骤，直到提取完所有元素。
1.2 示例
输入： array = [ [1, 2, 3], [8, 9, 4], [7, 6, 5] ]
输出： [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
1.3 限制
- 0 <= array.length <= 100
- 0 <= array[i].length <= 100
1.4 解题思路
根据题目示例 array = [ [1, 2, 3], [8, 9, 4], [7, 6, 5] ]，对应的输出为 [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]，可以发现，顺时针打印矩阵的顺序是 “从左向右、从上向下、从右向左、从下向上” 循环。
解题过程：
- 判断
arr是否为空值，如果为空直接返回[ ]即可； - 初始化左边界，右边界，上边界，下边界分别为
l，r，t，b，并创建容器res用于存储要打印的结果； - 循环打印： “从左向右、从上向下、从右向左、从下向上” 四个方向循环打印；
- 将按顺序添加到
res中 - 打印一行或一列，让边界收缩 1，代表已经打印
- 判断边界是否相遇，如果相遇则打印完毕，跳出循环。
- 将按顺序添加到
- 返回
res
文章来源：https://www.toymoban.com/news/detail-755130.html
c++代码
class Solution {
public:
vector<int> spiralArray(vector<vector<int>>& array) {
if (array.empty()) return {};
vector<int> res;
int l = 0, r = array[0].size() - 1;
int t = 0, b = array.size() - 1;
while(true)
{
//从左向右
for(int i = l; i <= r; i++) res.push_back(array[t][i]);
if(++t > b) break;
//从上向下
for(int i = t; i <= b; i++) res.push_back(array[i][r]);
if(--r < l) break;
//从右向左
for(int i = r; i >= l; i--) res.push_back(array[b][i]);
if(--b < t) break;
//从下向上
for(int i = b; i >= t; i--) res.push_back(array[i][l]);
if(++l > r) break;
}
return res;
}
};
📝结语
今天的干货分享到这里就结束啦！如果觉得文章还可以的话，希望能给个三连支持一下，聆风吟的主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是作者前进的最大动力！
文章来源地址https://www.toymoban.com/news/detail-755130.html
到了这里，关于【剑指offer|图解|数组】寻找文件副本 + 螺旋遍历二维数组的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
