首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

数组中重复的数字

题目描述 在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。...例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是第一个重复的数字2。 解题思路 最简单的就是用一个数组或者哈希表来存储已经遍历过的数字,但是这样需要开辟额外的空间。...如果题目要求不能开辟额外的空间,那我们可以用如下的方法: 因为数组中的数字都在0~n-1的范围内,所以,如果数组中没有重复的数,那当数组排序后,数字i将出现在下标为i的位置。...现在我们重排这个数组,从头到尾扫描每个数字,当扫描到下标为i的数字时,首先比较这个数字(记为m)是不是等于i。...如果是,则接着扫描下一个数字;如果不是,则再拿它和m 位置上的数字进行比较,如果它们相等,就找到了一个重复的数字(该数字在下标为i和m的位置都出现了),返回true;如果它和m位置上的数字不相等,就把第

2.1K30
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    获取不连续数字中缺的数字

    且将断号的号码找出来。 需求分析 凭证的短号规则,也就是这个凭证是通过怎么一个规则来判断短号的。最后和产品了解每个公司都有自己的规则。不一定是纯数字,也有可能标记有横杠特殊字符等。...砍需求,由于我们在年底进行开发的版本是POC版本,并且时间非常的紧急(以至于我们每天都要搞到11点)。所以说不用很复杂的业务需求,所以最后讨论下来先做为写死的纯数字校验。 所以有了今天这篇文章。...CODOING 其实有很多同学看到这个一串数字断号校验,这有什么可讲的呢?简单的一批。 刚开始的思路:这些数字有可能从零开始,也有可能从一开始,也有可能从。也有可能中间有很多断号的等等。。。。...min = (long) objects[0]; min <= max; min++) { integers.add(min); } //返回缺失的数字...100个短号那就采用只获取第一个短号 if(max - min > 100){ for (int i = 0; i < nos.size()-1

    2.1K30

    查找数组中重复的数字

    题目来源于《剑指Offer》中的面试题3:找出数组中重复的数字。   // 题目:在一个长度为n的数组里的所有数字都在0到n-1的范围内。...数组中某些数字是重复的,但不知道有几个数字重复了,   // 也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。...例如,如果输入长度为7的数组{2, 3, 1, 0, 2, 5, 3},   // 那么对应的输出是重复的数字2或者3。        ...: (输出) 数组中的一个重复的数字 // 返回值: // true - 输入有效,并且数组中存在重复的数字 // false - 输入无效,或者数组中没有重复的数字...numbers, sizeof(numbers) / sizeof(int), duplications, sizeof(duplications) / sizeof(int), true); } // 数组中存在多个重复的数字

    4K60

    数组中的重复数字

    """描述在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。...例如,如果输入长度为7的数组[2,3,1,0,2,5,3],那么对应的输出是2或者3。...存在不合法的输入的话输出-1数据范围:0\le n \le 10000 \0≤n≤10000进阶:时间复杂度O(n)\O(n) ,空间复杂度O(n)\O(n)示例1输入:[2,3,1,0,2,5,3]复制返回值...:2复制说明:2或3都是对的数据范围:0\le n \le 10000 \0≤n≤10000进阶:时间复杂度O(n)\O(n) ,空间复杂度O(n)\O(n)"""# @param numbers int...整型一维数组# @return int整型#from typing import Listclass Solution: def duplicate(self , numbers: List[int

    1.4K10

    获取数组中最小的k个数字_29

    思路:利用小根堆 面试或者其他啥情况估计是不允许大家直接用优先级队列的,所以我们还是老老实实的实现一个堆结构吧; 关于堆的结构以及其相应实现大家可以看我之前的一个笔记https://www.jianshu.com...notebooks/40413732/notes/55370532 我们这里和普通堆排序和堆数据修改有一点区别,那就是这里我们需要先实现一个小根堆,然后每一次拿第一个数据然后把这个数据删掉,但是我们这里存在一个问题,数组不太好删数据...,删除的话要进行一个所有数据的前移,因此, 我这里取了个巧,我把第一个数字和最后一个数字交换,然后我当这个数组的长度减了1,当最后一个数字不存在,然后会进行一个从顶到下的重建,同理第二大的数字出来后与倒数第二个交换...currIndex); } } /** * 堆平衡 * 当某个节点发送变化了,那么其子树就需要重新维持平衡 * param 堆,修改位置,堆数组大小...currIndex); } } /** * 堆平衡 * 当某个节点发送变化了,那么其子树就需要重新维持平衡 * param 堆,修改位置,堆数组大小

    40810

    javascript数组怎么定义_js中的数组

    初识数组:新建一个数组 每一门编程语言,都有数组或类似数组的结构,同样的JavaScript(虽然是脚本语言)也不例外,学习JavaScript的数组,我们从新建第一个数组开始: var arr = [...(arr[1]) 赋值的方法也很简单,直接给数组对应的索引值的位置赋值即可与其他编程语言不同的是: JavaScript中的数组,长度是动态可变的,如果学过其他编程语言的朋友可能对这一点不是很习惯。...]; var num2 = arr[1]; var num3 = arr[2]; 这样三个num变量就获取了数组arr的前三个元素,完成了访问。...认识数组:数组的基本方法 学会了新建数组和访问数组元素,我们开始了解一些数组的基本方法: push()方法 push(参数1,参数2,参数3…,参数n) 方法可把参数指定的元素依次添加到数组的末尾,...arr[0] + " " + arr[1] + " " + arr[2] + " " + arr[3] + " " + arr[4]); ---- slice()方法 slice() 方法返回包含从数组对象中的

    3.1K40

    JS中的数组方法

    JS中的数组方法总结 Array.push() 向数组的末尾添加一个或者多个元素,并返回新的长度 let arr =[1,2,3]; console.log(arr.push(6)) //打印结果为...(arr) //打印结果 [1,a] Array.slice(a,b) 将数组中的一部分选取出来并返回成新数组,不改变原数组,不包括结束位置。...的指向,对数组进行循坏遍历,fn可传三个参数fn(item,[index],[arr]),item为遍历过程中的当前元素,index为当前元素的下标,arr为原数组对象 let myArr = [1,2,3...this指向,因此如果想用thisValue参数必须使用function函数 Array.map() 对数组中的每个元素进行重新编辑,返回用编辑结果组成的新数组,传递的参数和forEach()一样...) //结果 2 Array.findIndex() 返回数组中符合条件的第一个元素的下标,若数组中没有元素符合要求则返回-1,不改变原数组 let arr = [1,2,3] console.log

    6.2K21

    JS中特殊的对象-数组

    属性获取数组的长度 console.log(arr3.length); // 可以设置length属性改变数组中元素的个数 arr3.length = 0; console.log(arr3[0]);...特别注意:JS中不像PHP,没有关联数组. 1.2 获取数组元素 // 格式:数组名[下标] 下标又称索引 // 下标从0开始 // 功能:获取数组对应下标的那个值,如果下标不存在,则返回undefined..."pink"; 1.5 数组操作案例 案例1:求数组中的所有数的和 //求和 var arr = [10, 20, 30, 40, 50]; //定义变量存储和 var sum = 0; for (var...i = 0; i < arr.length; i++) { sum += arr[i]; } console.log("和为:" + sum); 案例2:获取数组中的最大值 //最大值 var...){ console.log(arr[i]); } } 案例4:将数组转为字符串并以 | 分割 //把数组中的每个名字后面拼接一个|然后以字符串的方式输出 var names =

    9.1K00

    寻找数组中的重复数字

    它的规则如下: 给定一个长度为n的数组,数组中每个元素的取值范围为:0~n-1 数组中某些数字是重复的,但是不知道哪些数字重复了,也不知道重复了几次 求数组中任意一个重复的数字 实现思路 这个问题的实现思路有三种...排序方法实现 用排序方法实现分为两步: 先用快速排序对数组进行排序 遍历排序好的数组,如果其相邻的两个元素相等就代表数组中有重复的数字,将其返回即可。 接下来,我们通过一个例子来验证下上述思路。...哈希表辅助实现 我们可以额外声明一个哈希表,然后遍历数组,判断数组中的元素是否已存在于哈希表中,如果不存在就将其放入哈希表中,否则就代表数组中有重复元素,将其返回即可。...返回找到的重复数字 时间复杂度分析:遍历数组,判断哈希表中是否包含当前遍历到的元素时,都可以用O(1)的时间复杂度完成,所有元素遍历完就需要n个O(1),因此总的时间复杂度为O(n) 空间复杂度分析:...动态排序法实现 根据题意可知,数组中元素的取值范围在0~n-1,那么就可以得到如下结论: 如果数组中没有重复元素,那么第i号元素的值一定是当前下标(i) 如果数组中有重复元素,那么有些位置可能存在多个数字

    1.4K10
    领券