剑指Offer【3(2)】：不修改数组找出重复的数字

SoapEye 发布于2019-08-19 11:37 / 1260人阅读

摘要：题目在一个长度为的数组里面的所有数字都在的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为的数组，那么对应的输出是重复的数字或者。

题目

在一个长度为n+1的数组里面的所有数字都在1~n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为9的数组{2,3,5,4,3,2,6,7}，那么对应的输出是重复的数字2或者3。

方法一

创建一个长度为n+1的辅助数组，将原数组逐一复制到辅助数组中。如果原数组被复制的数字为m，则将它复制到辅助数组中下标为m的位置。

时间复杂度：O(n)，空间复杂度：O(n)

public static boolean test(int[] array){
        if(array == null || array.length<=0){
            return false;
        }
        
        for(int i=0;i=array.length || array[i]<=0){
                return false;
            }
        }
        int[] arr = new int[array.length];
        for(int i=0;i
参考：《剑指Offer》

云服务器 GPU云服务器不重复随机数组找出一个二维数组中的鞍点 js查找数组中重复的 WebRTC源码offer不触发事件

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/77569.html

剑指Offer【3】：数组中重复的数字

摘要：题目描述在一个长度为的数组里的所有数字都在到的范围内。请找出数组中任意一个重复的数字。例如，如果输入长度为的数组，那么对应的输出是第一个重复的数字。判断数组是否为空参考剑指题目描述在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2,...

vpants 2019-08-19 11:37 评论0 收藏0
剑指offer之基础知识数组

摘要：附上和实现二维数组中的查找题目描述在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。为了实习的准备，开始刷题来巩固基础算法和数据结构，大神轻喷。 1.数组中重复的数字题目描述：在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有...

zhou_you 2019-08-22 13:49 评论0 收藏0
【剑指 Offer II】 082. 含有重复元素集合的组合

摘要：题目给定一个可能有重复数字的整数数组和一个目标数，找出中所有可以使数字和为的组合。中的每个数字在每个组合中只能使用一次，解集不能包含重复的组合。示例输入输出示例输入输出提示注意本题与主站题相同答案回溯法排序后去重 ...

XUI 2021-11-12 10:36 评论0 收藏0
剑指offer--JavaScript版

摘要：剑指在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。例如输入前序遍历序列和中序遍历序列，则重建二叉树并返回。其中负数用补码表示。本文为8月牛客网《剑指 offer》刷题做得，现整理出来作为参考。虽然是算法题，但本文用 JavaScript 编写，看了《剑指 offer》以后发现很多问题处理的过程并不是最好的，所以本文仅供参考。以前全部代码 A...

MarvinZhang 2019-08-23 11:52 评论0 收藏0
【剑指offer系列刷题】第一篇——寻找单身狗

摘要：剑指系列刷题第一篇题目来源数组中数字出现的次数大家可以去测试一下自己的代码博主码云链接文章目录前言题目描述解题思路解题代码前言这是剑指系列刷题第一篇文章，大家可以互相学习一下。其中的两个单身狗是和。 ...

xavier 2021-10-12 10:12 评论0 收藏0