编程面试题2:在数组中寻找重复值

#未分类14:2621

众译鸣谢

原文字幕:[B]One静茹于2017.07.27制作完成

译文字幕:[B]刀子于2017.08.07制作完成

审核过程:3

字幕详情

你们今天过得怎样?
今天我想跟你们分享另一个编程面试题
题是这样的:
写一个函数来判断列表里是否有重复值
所以首先我们要做的就是分解问题
比如说我们有这么一个数组
数组里有6个元素
分别是1 2 3 3 4 和 5
可以看出数组中有两个重复值
3 和 3
那我们怎么来确定一个数组中有重复值呢?
我们首先会想到的就是去创建一个循环
这个循环去遍历数组中的每个元素
这样我们就能去检验数组中每个元素
但是我们可以再想的深入些
比如用嵌套循环
当我们用嵌套循环时
其实就是一个循环中又套了另一个循环
第一层循环中 我们遍历整个数组
这样我们就能提取到数组中的每个元素
第二层循环会用遍历到的元素去和数组中其他元素比较
我们创建了第二层循环后
就在第二层循环里添加一个 if 判断
这个判断会检查当前元素
是否和数组中另一个元素相等
当然我们也要确定
我们正在比较的两个元素
位置是不同的
一旦这两个条件符合
那么就可以确定数组中确实有重复值了
所以为了让大家更清楚一些
让我们来过一遍代码吧
好的 我们要做的第一件事
就是先创建一个函数
public static void checkForDuplicates
这就是我们给函数起的名字
在函数内部 我们要传递一个参数
这个参数就是那个整数数组
[打字中]
myArray
[打字中]
就像这样
现在我想在这写个注释
大概就是和我之前在讲义中
给你们展示的元素差不多
[打字中]
好的 让我们来检查一下这个数组
将这个数组传递到我们的函数中
这些就是数组所包含的元素
首先我们先创建一个 for 循环
我会这么写
[打字中]
for int i = 0
i < myArray.length
i++
[打字中]
一个基本的循环 就如你看到的
我们从第一个位置开始 这里就是1
然后我们就要遍历这个数组中的所有元素
就像我在讲义里刚才说的那样
我要再写一个循环 这个循环就叫做嵌套循环
其实就是一个循环在另一个循环里面
当我们要写这个循环的起始值时 我们其实想让它从
[打字中]
i + 1 开始
我们这么做的原因是
我们不想检查一个元素
我们不能拿同一个元素进行比较
所以我们从当前位置开始
然后将位置往后挪一位
我们不要从第一个位置开始遍历
因为这样就会和第一层循环的元素重合
好的 接下来就和前面的循环差不多了
除了起始点不一样
[打字中]
数组长度 j++
在嵌套的第二层循环里面
我们要加一个 if 判断语句
所以如果 i 位置的元素
等于 myArray 中
位置 j 的元素 这里
这里我们要
比较 i 位置的元素
和 j 位置元素的值
我们要比较它们的值是否相等
我们也要确定
i 和 j 不是同一个位置
所以这里我们要检查
当前位置和其他元素
所以这里我做的就是
检查 i 位置的元素
如果等于 j 位置的元素
并且它们的位置不同
这样重复值就是存在的了
这里我要写个打印函数
然后写句“重复值存在”
这差不多就是这个函数最终的样子了
接下来就是写主方法了
加上一个整数数组
[打字中]
这样做好后 我要复制这些
粘贴在这里 加上分号
现在我们调取这个函数
来检查我传递的数组中是否有重复值
就像你们在这里看到的这样
现在如果运行这个程序 应该会在控制台上打印出这些内容
对吧?确实存在一个重复值
好的 这就是如何去找到
数组中是否存在重复值的方法
另一个需要注意的地方就是这个函数有两层循环
这意味着时间复杂度
[打字中]
等于O(n²)
好的 这里的时间复杂度O(n²)并不是理想的时间复杂度
其实有方法可以降低这个时间复杂度
降到只有一元线性复杂度上
让我们回到讲义中
好的 现在你怎样能让这个函数的性能更好呢
可以这样做
首先考虑一下两层循环的结构
我们已经看到这个循环了
这是个嵌套循环
就像我说的 它的时间复杂度是 n 的平方
现在你可以只用一个 for 循环
这个 for 循环的时间复杂度是 n 或者说是一元线性复杂度
所以我们想用这么一个 for 循环
用这个 for 循环的目的
是为了减少时间复杂度
另一个我们要用的东西是集合
集合是一堆没有重复值的数的无序组合
它和数组不同
因为数组允许它里面的元素有重复值
但是集合的元素必须是唯一的
接下来我来给你们展示如何创建
一个集合 就像这样
你要给集合起个名字 要确定它的数据类型
让后让它成为一个散列集的实例
好的 让我们回到代码中
我来展示怎么做
好的 我要创建另一个函数
static void checkForDuplicates
我们就在之前函数的名字后加上 withset 吧
就这么叫它吧
现在我们还是做一样的事 我们要传递
myArray这个数组 好的
然后我们这么做
首先创建一个集合
[打字中]
等于一个新的散列集实例
好的 这个集合是整数型的
然后引用散列集这个类
好的 这就是我们要做的
我们要来创建一个 foreach 的循环
基本是我们要做的就是这个
我们想要 if 不对 我们想要 for 来遍历
我们数组中的每个整数
[打字中]
然后增加一个 if 判断
[打字中]
如果myset.add(x)
[打字中]
等于false 那么
[打字中]
就打印出“存在一个重复值”
差不多就是这样了
[打字中]
基本上就是我所写的这样了
我创建了一个集合
然后给这个集合添加了一个值
就像我在讲义中说的一样 让我们快速回顾一下
讲义中差不多就是这样写的
集合中的每个元素必须是唯一的
如果你想加入一个重复值
是不会成功的
如果你加了一个重复值 集合会返回一个 false
就像现在这样
mySet.add(x)
如果这个值等于 false 那么就意味着有重复值存在
我们测试一下代码
先复制这些 然后回到我们的主方法
粘贴 传递这里这个数组
我们还是用相同的数组列表
好的 我们运行一下这个程序 先来清空之前的记录
然后运行这个程序 就用我们刚写的新方法
好的 运行程序
存在一个重复值
我们也能把这个重复值打印出来
这里 这可以使结果更清楚
存在一个重复值
保存 然后再运行
这个重复值就是 3
这个 foreach 循环的时间复杂度就是O(n)
好的 教程到这里就要结束了
如果你有任何问题 就在下面留言吧
如果你感觉从视频里学到了东西 别忘了给视频点赞
当然别忘了订阅我 我们下次见
以下内容有剧透 , 请注意打开姿势

精彩推荐

  • #4 Kotlin教程 | Class类 | Object对象

    05:5111

  • #7 Kotlin教程 | 把Java转换为Kotlin

    02:148

  • 数据结构:哈希表

    06:242

  • 如何处理行为举止问题

    05:3114

  • 大写O符号

    08:366

  • 数据结构:字典树

    04:5429

  • 3个算法策略

    07:0013

  • 马丘比丘

    07:35201

更多视频, 请移步译学馆APP欣赏  GET APP