【剑指offer|图解|数组】寻找文件副本 + 螺旋遍历二维数组

🌈个人主页：聆风吟
🔥系列专栏：数据结构、剑指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 解题思路二

哈希表
利用数据结构特点，容易想到使用哈希表记录数组的各个数字，当查找到重复数字则直接返回。

1. 初始化： 新建 HashSet ，记为 map ；
2. 遍历数组 documents 中的每个数字 doc：
   1. 如果doc在hmap中，说名重复，直接返回doc;
   2. 如果不在，将doc添加至hmap中；
3. 如果不存在，返回-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 ]，可以发现，顺时针打印矩阵的顺序是 “从左向右、从上向下、从右向左、从下向上” 循环。

解题过程：

1. 判断 arr 是否为空值，如果为空直接返回 [ ] 即可；
2. 初始化左边界，右边界，上边界，下边界分别为 l，r，t，b，并创建容器 res 用于存储要打印的结果；
3. 循环打印： “从左向右、从上向下、从右向左、从下向上” 四个方向循环打印；
   1. 将按顺序添加到 res 中
   2. 打印一行或一列，让边界收缩 1，代表已经打印
   3. 判断边界是否相遇，如果相遇则打印完毕，跳出循环。
4. 返回 res

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;
    }
};

---

📝结语

???? 今天的干货分享到这里就结束啦！如果觉得文章还可以的话，希望能给个三连支持一下，聆风吟的主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是作者前进的最大动力！