首页
学习
活动
专区
工具
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

    数组中重复的数

    之前有写过 找出数组中只出现一次的数,今天再来看下怎么找出数组中重复出现的数。 有一个长度为 n 的数组,所有的数字都在 0~n-1 的范围,现在要求找出数组中任意一个重复的数字。...思路一: 先给数组排序,然后再遍历一遍有序数组,依次比较相邻元素,就很容易能找出数组中重复的值。使用快排排序的话时间复杂度为 O(nlogn) 。...思路二: 利用空间换时间的思想,新建一个哈希表,然后遍历数组,每扫描一个元素都去哈希表里查找是否也存在该元素,如果存在,即找到一个重复的数,如果不存在,则将该元素保存到哈希表。...思路三: 认真审题,你会发现有一些特点,长度为 n 的数组,且元素的大小范围为 0~n-1,如果没有重复的数字的话,那么数组排序后数字 i 就是下标 i 所在的位置了,即 arr[i] == i。...#arr数组中没有重复元素的情况 #数组长度为7,元素范围为0-6 arr = [0,1,2,3,4,5,6] arr[0] == 0 arr[1] == 1 arr[2] == 2 我们通过一个具体的例子来捋一捋思路

    1.7K20

    如何快速合并两个有序数组?

    前言 大家好,我是来自于华为的程序员小熊。今天给大家带来一道与数组相关的题目,这道题同时也是字节、微软和亚马逊等互联网大厂的面试题,即力扣上的第88题-合并两个有序数组。...本文主要介绍逆向双指针的策略来解答,供大家参考,希望对大家有所帮助。 合并两个有序数组 ?...❞ ❝策略二:双指针法,先开辟一个新数组,长度为两个数组的长度之和,然后让两个指针分别指向两个数组的头部,比较这个两个指针指向的数组元素的值,将数值较小的放到新数组的头部,再将指向的数值较小的指针右移,...❞ 「复杂度分析」 【时间复杂度】:策略一是O((n + m)lg(n + m)),主要是合并之后再排序的时间复杂度;策略二是O(n + m),主要是遍历两个数组的时间复杂度。...示例 按照题目要求,合并后的数组应该如下图示: ? 合并后的数组 先设置两个指针 p 和 q,分别指向两个数组的末尾,假设 k 为两数组的长度,如下图示: ?

    84630

    查找数组中重复的数字

    题目来源于《剑指Offer》中的面试题3:找出数组中重复的数字。   // 题目:在一个长度为n的数组里的所有数字都在0到n-1的范围内。...数组中某些数字是重复的,但不知道有几个数字重复了,   // 也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。...此处介绍自己的一个做法,以空间换时间,通过新建数组来实现快速查找,具体做法是新建长度为length的数组newArray,初始化值为-1;将numbers数组的值依次作为newArray的下标和对应的值为...: (输出) 数组中的一个重复的数字 // 返回值: // true - 输入有效,并且数组中存在重复的数字 // false - 输入无效,或者数组中没有重复的数字...,通过指针可以访问和修改指向的对象,但是拷贝的指针是两个不同的指针 // // 建议使用引用类型的形参替代指针 // if (numbers == nullptr || length <=

    4K60

    如何快速合并两个有序数组?

    ​前言 大家好,我是来自于「华为」的「程序员小熊」。今天给大家带来一道与「数组」相关的题目,这道题同时也是字节、微软和亚马逊等互联网大厂的面试题,即力扣上的第 88 题-合并两个有序数组。...❞ ❝ 策略二:双指针法,先开辟一个新数组,长度为两个数组的长度之和,然后让两个指针分别指向两个数组的头部,比较这个两个指针指向的数组元素的值,将数值较小的放到新数组的头部,再将指向的数值较小的指针右移...❞ 「复杂度分析」 【时间复杂度】:策略一是「O((n + m)lg(n + m))」,主要是合并之后再排序的时间复杂度;策略二是「O((n + m))」,主要是遍历两个数组的时间复杂度。...image.png 按照题目要求,合并后的数组应该如下图示: image.png 先设置两个指针 p 和 q,分别指向两个数组的末尾,假设 k 为 两数组的长度,如下图示: image.png 比较...往期精彩回顾 最大子序和 你不可不会的几种移动零的方法 专业小偷才能盗取最大金额的现金 手撕腾讯面试题-乘积最大子数组 茫茫人海,如何快速找到合适的 ta?

    1.1K00

    数组中的重复数字

    """描述在一个长度为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
    领券