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

2023-12-13 23:54:08

在这里插入图片描述
🌈个人主页:聆风吟
🔥系列专栏:数据结构剑指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. 初始化左边界,右边界,上边界,下边界分别为 lrtb,并创建容器 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;
    }
};


📝结语

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

文章来源:https://blog.csdn.net/2301_80026901/article/details/134895581
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。