博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
解决数组中重复的数字
阅读量:4841 次
发布时间:2019-06-11

本文共 1112 字,大约阅读时间需要 3 分钟。

今天写了一道算法题。

对于我这个菜鸟来说连看懂答案都是一件不容易的事情。

但是

路漫漫其修远兮 吾将上下而求索

所以我是不会泄气的,一定要加强修行,为了生活吧

这道题是剑指上的

看一下题目描述

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

我首先想到的最粗糙的方法就是双重for循环,不用说,这种方法肯定是不通过的,它的空间和时间的效率都不高

所以我选择看答案。

汗颜的是。。答案都不怎么理解。。

认真研究了一下,我这里用自己粗鄙的方式来描述一下吧

首先看代码

1    public static boolean duplicate(int[] nums, int length, int[] duplication) { 2         if (nums == null || length <= 0){ 3             return false; 4         } 5         for (int i=0;i
View Code

这是给大家看一下官方的解题思路

要求是时间复杂度 O(N),空间复杂度 O(1)。因此不能使用排序的方法,也不能使用额外的标记数组。对于这种数组元素在 [0, n-1] 范围内的问题,可以将值为 i 的元素调整到第 i 个位置上进行求解。以 (2, 3, 1, 0, 2, 5) 为例,遍历到位置 4 时,该位置上的数为 2,但是第 2 个位置上已经有一个 2 的值了,因此可以知道 2 重复:

可以说已经很通俗易懂了。

但我当时怎么就不理解呢。。

我这里说一下自己的看法吧,呃呃,言辞可能有些粗鄙,大家不要介意哈

我们看到,duplication方法接收三个参数,分别是数组,数组长度,和重复元素放置的数组

先判断一下空和长度,没毛病 

这里for循环开始遍历数组

这么说吧,假设由一百个数,如果每个数都是唯一的,那么它们都有一个唯一和值相对应的地址。可以理解为一百个人占坑

从头开始判断,看看这个坑是不是它自己的,如果是就留下,进入下一次循环,如果不是的话就判断一下这个坑有没有给人占了

如果发现,自己的坑有人占了!那么问题来了,这个人的标号跟自己肯定是相同的,也就是说出现了重复元素

如果未被占,那么就可以放心的去自己的坑,继续下一次循环,一直到发现重复元素或遍历结束返回true或者false

那么,今天的总结就这样

转载于:https://www.cnblogs.com/lwhblog/p/10639097.html

你可能感兴趣的文章
BUPT复试专题—中序遍历序列(2013)
查看>>
【常见Web应用安全问题】---7、CRLF injection
查看>>
php7.2.1 安装
查看>>
用winrar解压时提示无法设置安全数据 拒绝访问的解决方法
查看>>
诡异的数学,数字问题 - leetcode
查看>>
交换输出
查看>>
设计模式-策略模式&状态模式&访问者模式
查看>>
python学习第三十三节(IO模型)
查看>>
linux pci 驱动小结
查看>>
BZOJ2744: [HEOI2012]朋友圈
查看>>
设计模式之抽象工厂模式
查看>>
大整数相关的几道题
查看>>
利用表格实现大图轮播
查看>>
SpringBoot集成jsp
查看>>
HTML+CSS 内容居中效果
查看>>
关于对话框
查看>>
Jmeter-元件的作用域和执行顺序
查看>>
ArrayList集合
查看>>
Redis集群搭建与简单使用
查看>>
VS2010连接SQLite数据库
查看>>