每日一练(1):找出数组中重复的数字

简介: 在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。


示例 1:


输入:

[2, 3, 1, 0, 2, 5, 3]


输出:2 或 3


限制:

2 <= n <= 100000


来源:力扣(LeetCode)


链接:https://leetcode-cn.com/probl...


方法一:哈希表


算法流程:


  • 初始化: 新建 Hash
  • Set ,记为 dic ;
  • 遍历数组 nums 中的每个数字 num:
  • 当 num 在 dic 中,说明重复,直接返回 num ;
  • 将 num 添加至 dic 中;
  • 返回 -1 。本题中一定有重复数字,因此这里返回多少都可以。


复杂度分析:


  • 时间复杂度 O(N) : 遍历数组使用 O(N) ,HashSet 添加与查找元素皆为 O(1) 。
  • 空间复杂度 O(N) : HashSet 占用 O(N) 大小的额外空间。


int findRepeatNumber(vector<int>& num) {
    unordered_map<int, bool> map;
    for (int num : nums) {    //循环遍历
        if (map[num]) {
            return num;
        }
        map[num] = true;
    }
    return -1;
}


方法2:原地交换


算法流程:


  • 1.遍历数组 nums ,设索引初始值为 i = 0i=0 :


  • 1.若 nums[i] = i : 说明此数字已在对应索引位置,无需交换,因此跳过;
  • 2.若 nums[nums[i]] = nums[i] : 代表索引 nums[i] 处和索引 i 处的元素值都为 nums[i],即找到一组重复值,返回此值 nums[i] ;
  • 3.否则: 交换索引为 i 和 nums[i] 的元素值,将此数字交换至对应索引位置。


  • 2.若遍历完毕尚未返回,则返回 −1 。


复杂度分析:


  • 时间复杂度 O(N) : 遍历数组使用 O(N) ,每轮遍历的判断和交换操作使用 O(1) 。
  • 空间复杂度 O(1) : 使用常数复杂度的额外空间。


int findRepeatNumber(vector<int>& nums) {
    int i = 0, temp;
    while(i < nums.size()) {
        if(nums[i] == i) {
            i++;
            continue;
        }
        if(nums[nums[i]] == nums[i]) {
            return nums[i];
        }
        temp = nums[i];
        nums[i] = nums[temp];
        nums[temp] = temp;
    }
    return -1;
}


目录
相关文章
|
3天前
|
存储 关系型数据库 分布式数据库
PostgreSQL 18 发布,快来 PolarDB 尝鲜!
PostgreSQL 18 发布,PolarDB for PostgreSQL 全面兼容。新版本支持异步I/O、UUIDv7、虚拟生成列、逻辑复制增强及OAuth认证,显著提升性能与安全。PolarDB-PG 18 支持存算分离架构,融合海量弹性存储与极致计算性能,搭配丰富插件生态,为企业提供高效、稳定、灵活的云数据库解决方案,助力企业数字化转型如虎添翼!
|
14天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1305 5
|
13天前
|
机器学习/深度学习 人工智能 前端开发
通义DeepResearch全面开源!同步分享可落地的高阶Agent构建方法论
通义研究团队开源发布通义 DeepResearch —— 首个在性能上可与 OpenAI DeepResearch 相媲美、并在多项权威基准测试中取得领先表现的全开源 Web Agent。
1333 87
|
2天前
|
弹性计算 安全 数据安全/隐私保护
2025年阿里云域名备案流程(新手图文详细流程)
本文图文详解阿里云账号注册、服务器租赁、域名购买及备案全流程,涵盖企业实名认证、信息模板创建、域名备案提交与管局审核等关键步骤,助您快速完成网站上线前的准备工作。
184 82
2025年阿里云域名备案流程(新手图文详细流程)
|
7天前
|
前端开发
Promise的then方法返回的新Promise对象的状态为“失败(Rejected)”时,链式调用会如何执行?
Promise的then方法返回的新Promise对象的状态为“失败(Rejected)”时,链式调用会如何执行?
242 127