代码编织梦想

剑指offer 03.数组中重复的数字

题目链接

  1. 题目描述:
在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1:
输入:
[2, 3, 1, 0, 2, 5, 3]
输出:23 
 
限制:
2 <= n <= 100000
  1. 思路:
第一思路:
开辟新的空间(数组或者map)标记已经出现过的数字,
时间复杂度O(N),空间复杂度O(N)

优化思路:
不开辟新的空间,在原数组上标记,时间复杂度O(N),空间复杂度O(1)

具体解释:
把数字i交换到下标为i的位置,使得数字与下标对应,
那么该数字再次出现时就可以判断重复。
  1. 代码
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        int i = 0;
        while(i < nums.size()) {
            if(nums[i] == i) {
                i++;
                continue;
            }
            if(nums[nums[i]] == nums[i])
                return nums[i];
            swap(nums[i],nums[nums[i]]);
        }
        return -1;
    }
};
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_45889838/article/details/127992680

三种方法详解:剑指Offer 03. 数组中重复的数字-爱代码爱编程

LeetCode:剑指Offer 03. 数组中重复的数字 文章目录 LeetCode:剑指Offer 03. 数组中重复的数字原题LeetCode链接:[剑指Offer 03. 数组中重复的数字](https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/)题目:

剑指offer 03. 数组中重复的数字(利用set的奇异性)-爱代码爱编程

1.题目描述 2.题解思路 由于题目只需要找到任意一个重复的数字,因此可以遍历数组,同时将遇到的每一个数组加到集合中,如果出现添加失败的情况,就代表该数字已经添加过一遍了。 算法: 初始化一个空集合遍历数组,并添加数字进行集合如果添加失败,就说明元素已经在集合中,直接返回即可 3.代码 class Solution { p

剑指Offer03.数组中重复的数字 c++实现-爱代码爱编程

剑指Offer03.数组中重复的数字 c++实现 写在前面,小白从零刷题,在解答会写出思路,正确答案,以及所有使用到的语法和知识点 1. 使用集合 思路就是利用集合不能有重复数字的这个特性,把数组中的元素依次送入集合当中,判断一下这个元素是否被送入,如果已经被送入,那么返回该值,这样得到的是第一个重复的元素class Solution { publi

剑指 Offer 03. 数组中重复的数字C++-爱代码爱编程

题目描述:在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。![在这里插入图片描述](https://img-blog.csdnimg.cn/20200807215155545.png?x-oss-process=imag

Leetcode 剑指 Offer 03. 数组中重复的数字-爱代码爱编程

剑指 Offer 03. 数组中重复的数字 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof 著作权归领扣网络所有。 找出数组中重复的数字。 在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内

剑指 Offer 03. 数组中重复的数字的4种解法(Java语言)-爱代码爱编程

题目详情 找出数组中重复的数字。 在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。 示例 1: 输入: [2, 3, 1, 0, 2, 5, 3] 输出:2 或 3 解法一:暴力法,双层循环 直接进行两层循环

剑指 Offer 03. 数组中重复的数字(python3编写)-爱代码爱编程

目录 1、题目描述:2、方法一:排序思路:代码:3、方法二:哈希表思路:代码:4、方法三:原地交换思路:代码: 1、题目描述: 2、方法一:排序 思路: 首先将数组从小到大排序;然后再遍历一遍数组,检查相邻元素是否相等,若相等则找到了一个重复的元素,直接返回这个元素即可。 代码: class Solut

剑指 Offer 03. 数组中重复的数字(JavaScript语言)-爱代码爱编程

思路一(使用集合法) 初始化一个集合。遍历数组,如果该数字未出现在集合中,将其加入到集合中,如果出现,该数字就为符合题意的数字。 代码 /** * @param {number[]} nums * @return {number} */ var findRepeatNumber = function(nums) { var set = ne

剑指 offer03. 数组中重复的数字 -- JavaScript解法-爱代码爱编程

题目描述 思路 && Code 方法一,对数组进行排序,如果存在重复的元素,元素肯定相邻,从头到位扫描排序后的数组做对比即可。 var findRepeatNumber = function(nums) { nums.sort((a,b) => { return a - b; }) for(let i =

剑指Offer03.数组中重复的数字-爱代码爱编程

文章目录 剑指Offer03.数组中重复的数字题解-哈希表题解-原地交换 剑指Offer03.数组中重复的数字 找出数组中重复的数字。 在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。 示例 1: 输

《剑指offer》03.数组中重复的数字-爱代码爱编程

03.找出数组中重复的数字 1.找出数组中重复的数字。2.不修改数组找出重复的数字 1.找出数组中重复的数字。 LeetCode:剑指offer03.数组中重复的数字 问题描述: 在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组

剑指 offer 03. 数组中重复的数字_喽耶的博客-爱代码爱编程

找出数组中重复的数字。 在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。 示例 1: 输入:[2, 3, 1, 0, 2, 5, 3] 输出:2 或 3 哈希查找 使用哈希表,因为哈希表判断是否存在的

剑指offer03. 数组中重复的数字【简单】_伍六琪的博客-爱代码爱编程

剑指 Offer 03. 数组中重复的数字 题目描述: 找出数组中重复的数字。 在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。 示例 1: > 输入: [2, 3, 1, 0, 2, 5, 3] &g

剑指 offer 03. 数组中重复的数字_701044的博客-爱代码爱编程

本文用于学习记录 文章目录 前言一、python 内置函数1. set() 函数2. range() 函数3. len() 方法 二、python 集合方法1. add() 方法 三、剑指 Off

通关算法题之 ⌈二叉树⌋ 上_海岸星的清风的博客-爱代码爱编程

二叉树深度 104、求二叉树最大深度 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数,叶子节点是指没有子节点的节点。 示例: 给定二叉树[3,9,20,null,null,15,7], 3 /

力扣 217. 存在重复元素 --- c语言求解_thepak的博客-爱代码爱编程

题目描述: 给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ,返回 true ;如果数组中每个元素互不相同,返回 false 。 题解: 如果暴力遍历的方法会超出时间限制,官方给出两种求解。分别是使用哈希表和排序求解。 方法1. 使用哈希表 思路:首先定义一个哈希表。遍历数组 ,每读取一个元素判断哈希表中是否有该元素,没有则将该元

11.20二叉树基础题型_小白孙在路上的博客-爱代码爱编程

一.二叉树的存储 1.存储结构 存储结构:顺序存储或者是类似于链表的链式存储 二叉树的链式存储是通过一个一个的节点引用起来的,常见的表示方式有二叉和三叉表示方式 // 孩子表示法 class Node { int val; // 数据域 Node left; // 左孩子的引用,常常代表左孩子为根的整棵左子树 Node right; /

代码随想录刷题|leetcode 343. 整数拆分 96.不同的二叉搜索树_symdunstaz的博客-爱代码爱编程

目录 343. 整数拆分 思路 整数拆分 96.不同的二叉搜索树 思路 不同的二叉搜索树 343. 整数拆分 题目链接:力扣 思路         动态规划的题目虽然说是要先确定dp数组的含义,再确定递归公式,但是总感觉这两者是相辅相成的,是一起出来的,但是到此,dp数组代表的都是我们要求取

剑指 offer 03. 数组中重复的数字-爱代码爱编程

找出数组中重复的数字。 在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。 示例 1: 输入: [2, 3, 1, 0, 2, 5, 3] 输出:2 或 3    限制: 2 <= n <= 1000

代码随想录训练营第28天|leetcode 93.复原ip地址、78.子集、 90.子集ii-爱代码爱编程

参考 代码随想录 题目一:LeetCode 93.复原IP地址 确定递归参数和返回值 参数:字符串s,下一个起始位置startIndex,添加’.'的数量pointNum vector<string> r