ADM-201 dump PMP dumps pdf SSCP exam materials CBAP exam sample questions

编程面试题2:在数组中寻找重复值 – 译学馆
未登录,请登录后再发表信息
最新评论 (0)
播放视频

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

IQ 2: How to write a function that finds duplicate values in an array?

你们今天过得怎样?
How are you guys doing today?
今天我想跟你们分享另一个编程面试题
Today I have another coding interview problem that I want to share with you guys.
题是这样的:
So here’s the problem:
写一个函数来判断列表里是否有重复值
Write a function that detects if a list has duplicate values.
所以首先我们要做的就是分解问题
So the first thing we want to do is to break down the problem.
比如说我们有这么一个数组
So let’s just say we have an array.
数组里有6个元素
Inside this array, we have six elements.
分别是1 2 3 3 4 和 5
We have 1, 2, 3, 3, 4 and 5.
可以看出数组中有两个重复值
As you notice in this array, we have 2 repeating values.
3 和 3
Three and three.
那我们怎么来确定一个数组中有重复值呢?
How do we go about determining if an array has duplicate values?
我们首先会想到的就是去创建一个循环
Well the first thing that may come to mind is to create a loop.
这个循环去遍历数组中的每个元素
A loop what iterate through each element within this array,
这样我们就能去检验数组中每个元素
and we’ll be able to take note of each element within this array.
但是我们可以再想的深入些
But we want to think about this a little bit deeper.
比如用嵌套循环
and that brings me to nested loops.
当我们用嵌套循环时
So when we deal with nested loops,
其实就是一个循环中又套了另一个循环
Well nested loops in itself is just a loop inside of another loop.
第一层循环中 我们遍历整个数组
The first loop, when we iterate it to this array
这样我们就能提取到数组中的每个元素
we just take note of each element within the list.
第二层循环会用遍历到的元素去和数组中其他元素比较
Whereas the second element will compare the current element with each element in the array.
我们创建了第二层循环后
Once we have that second loop,
就在第二层循环里添加一个 if 判断
inside of that second loop, we want to add an if condition,
这个判断会检查当前元素
that will check if the current element in array
是否和数组中另一个元素相等
is equal to another element in the array.
当然我们也要确定
and we also want to make sure that the elements
我们正在比较的两个元素
that we are comparing against each other.
位置是不同的
have a different position
一旦这两个条件符合
and of those two things are satisfied
那么就可以确定数组中确实有重复值了
then a duplicate element exist within the list.
所以为了让大家更清楚一些
So to make this a little bit more clear,
让我们来过一遍代码吧
let’s start coding.
好的 我们要做的第一件事
Alright, so the first thing we want to do
就是先创建一个函数
we wanna create ourselves a function.
public static void checkForDuplicates
public static void checkForDuplicates
这就是我们给函数起的名字
That’s what we’re gonna name our function.
在函数内部 我们要传递一个参数
Now inside this function, we also want to pass in a parameter.
这个参数就是那个整数数组
Now the parameter is yet gonna consist of the array list of integers.
[打字中]
[Typing]
myArray
myArray
[打字中]
[Typing]
就像这样
Just like that.
现在我想在这写个注释
So what I want to do right now is to write a comment
大概就是和我之前在讲义中
that is pretty much gonna the resemble the elements
给你们展示的元素差不多
that I showed you earlier in my presentation.
[打字中]
[Typing]
好的 让我们来检查一下这个数组
Alright, so let’s just say we are checking this array right here.
将这个数组传递到我们的函数中
and just say this is the array that is passed in to this array here.
这些就是数组所包含的元素
These are the elements that are contained here.
首先我们先创建一个 for 循环
So the first thing we want to do is to create a for loop
我会这么写
which will go something like this.
[打字中]
[Typing]
for int i = 0
for int i =0
i < myArray.length
i < myArray.length
i++
i++
[打字中]
[Typing]
一个基本的循环 就如你看到的
A basic loop. As you can see here,
我们从第一个位置开始 这里就是1
we’re starting at position one, which would be one,
然后我们就要遍历这个数组中的所有元素
and then, from here we’re just gonna iterate through each element within this array.
就像我在讲义里刚才说的那样
Now, as I say in the presentation,
我要再写一个循环 这个循环就叫做嵌套循环
I wanna add another loop, and this for loop is gonna called a nested for loop.
其实就是一个循环在另一个循环里面
Basically just a loop inside of another loop.
当我们要写这个循环的起始值时 我们其实想让它从
Now, when we’re starting this loop off, we actually wanna start
[打字中]
[Typing]
i + 1 开始
with i plus one.
我们这么做的原因是
Now the reason we’re doing this is because
我们不想检查一个元素
we don’t want to check for any value,
我们不能拿同一个元素进行比较
we don’t want to go over any of the same value.
所以我们从当前位置开始
So we wanna start with the current position,
然后将位置往后挪一位
and we wanna add plus one.
我们不要从第一个位置开始遍历
We don’t want to iterate, we don’t want to start it at zero,
因为这样就会和第一层循环的元素重合
because we don’t want to count the same element.
好的 接下来就和前面的循环差不多了
Alright, so this is pretty much that would look similar to our previous loop.
除了起始点不一样
just except the starting point.
[打字中]
[Typing]
数组长度 j++
at length, j plus plus.
在嵌套的第二层循环里面
Now inside this nested for loop
我们要加一个 if 判断语句
what we want to do is add an if conditional statement.
所以如果 i 位置的元素
So if that element at position i
等于 myArray 中
is equal to myArray.
位置 j 的元素 这里
at position j, so right here what we are doing
这里我们要
So I, right here we are doing, we’re…
比较 i 位置的元素
comparing the content of the element at position i
和 j 位置元素的值
as well as the content of the element at position j.
我们要比较它们的值是否相等
We’re trying to check and see if they are the same.
我们也要确定
And we also wanna make sure,
i 和 j 不是同一个位置
that i is not equal to j.
所以这里我们要检查
So right here what we are doing is just checking
当前位置和其他元素
the current position of each other elements.
所以这里我做的就是
So what I am doing here is checking
检查 i 位置的元素
if an element at position i,
如果等于 j 位置的元素
is equal to an element at position j.
并且它们的位置不同
and they are both at different positions,
这样重复值就是存在的了
then a duplicate exists.
这里我要写个打印函数
So I just wanna do a sysout
然后写句“重复值存在”
and then just write a duplicate exists.
这差不多就是这个函数最终的样子了
And that’s pretty much it that’s the final of the function though.
接下来就是写主方法了
Now what I want to do next is go up to this main method,
加上一个整数数组
and add an integer array.
[打字中]
[Typing]
这样做好后 我要复制这些
So done with something like this. I am just gonna copy this.
粘贴在这里 加上分号
Paste it here, the semicolon there.
现在我们调取这个函数
And now I wanna call this function,
来检查我传递的数组中是否有重复值
check for duplicate values that I am passing in my array.
就像你们在这里看到的这样
which you can see here.
现在如果运行这个程序 应该会在控制台上打印出这些内容
Now if I run this, I should get this content printed to the console.
Right? A duplicate exists.
对吧?确实存在一个重复值
Right? A duplicate exists.
Alright, so that’s how you go about finding
好的 这就是如何去找到
Alright, so that’s how you go about finding
if there are duplicates within the list.
数组中是否存在重复值的方法
if there are duplicates within the list.
Another thing that taken to account is that this function as two four loops.
另一个需要注意的地方就是这个函数有两层循环
Another thing that taken to account is that this function as two for loops.
which means that the time complexity
这意味着时间复杂度
which means that the time complexity
[打字中]
[Typing]
is equal to O of n square
等于O(n²)
is equal to O of n square
Alright, now this time complexity of O n if square is not the ideal time complexity.
好的 这里的时间复杂度O(n²)并不是理想的时间复杂度
Alright, now this time complexity of O of n square is not the ideal time complexity.
There is another way that you can actually reduce this time complexity.
其实有方法可以降低这个时间复杂度
There is another way that you can actually reduce this time complexity.
to only have a linear time complexity.
降到只有一元线性复杂度上
to only have a linear time complexity.
So let’s go back to the presentation.
让我们回到讲义中
So let’s go back to the presentation.
Alright, so how would you go about enhancing the function for better performance.
好的 现在你怎样能让这个函数的性能更好呢
Alright, so how would you go about enhancing the function for better performance.

可以这样做
This is what you would do.

首先考虑一下两层循环的结构
What you need to do is, first of all, consider these two loop structures,

我们已经看到这个循环了
So we already have seen this loop here,
这是个嵌套循环
which is a nested loop.

就像我说的 它的时间复杂度是 n 的平方
and as I say it before, it has a time complexity of n square.

现在你可以只用一个 for 循环
Now, what you want to do is actually use a for loop.

这个 for 循环的时间复杂度是 n 或者说是一元线性复杂度
This for loop is gonna have a time complexity of n or a linear time complexity.

所以我们想用这么一个 for 循环
So we want to use a for loop,

用这个 for 循环的目的
that’s the one thing that we want to use
是为了减少时间复杂度
in order to reduce that time complexity.

另一个我们要用的东西是集合
Another thing that we want to use is a set.

集合是一堆没有重复值的数的无序组合
Now a set is an unordered collection of values that can not have duplicates.

它和数组不同
It’s different from an array,

因为数组允许它里面的元素有重复值
because an array you are allowed to have duplicate elements or something in array,
但是集合的元素必须是唯一的
but when it comes to a set, every element in a set must be unique.

接下来我来给你们展示如何创建
And what I want to do is just show you how you could create
一个集合 就像这样
a collection of a set,like this.
你要给集合起个名字 要确定它的数据类型
You would have the name set, you have to specify the data type.
让后让它成为一个散列集的实例
And set it equals to a new HashSet.
好的 让我们回到代码中
Alright. So let’s get back to the code,
我来展示怎么做
now I’ll show you how to do this.
好的 我要创建另一个函数
Alright, so what I want to do is create another function.
static void checkForDuplicates
static void checkForDuplicates
我们就在之前函数的名字后加上 withset 吧
Let’s just call this subject for duplicates with set.
就这么叫它吧
Let’s just call it that.
现在我们还是做一样的事 我们要传递
Now we want to do the same thing, we just want to pass in
myArray这个数组 好的
the array myArray. Alright.
然后我们这么做
Now, when we do this,
首先创建一个集合
the first thing that we need to do is create a set
[打字中]
[Typing]
等于一个新的散列集实例
equals new HashSet
好的 这个集合是整数型的
Alright this is gonna take in integer,
然后引用散列集这个类
and then we have to import this.
好的 这就是我们要做的
Alright. So this is what we want to do now.
我们要来创建一个 foreach 的循环
We want to create ourselves a foreach loop.
基本是我们要做的就是这个
And basically what we want to do is this.
我们想要 if 不对 我们想要 for 来遍历
We wanna say if, or for, we wanna say for
我们数组中的每个整数
every integer that’s in my array.
[打字中]
[Typing]
然后增加一个 if 判断
We want to add an if conditional that states if
[打字中]
[Typing]
如果myset.add(x)
my set. add x
[打字中]
[Typing]
等于false 那么
equals false, then we wanna say,
[打字中]
[Typing]
就打印出“存在一个重复值”
I wanna print out “a duplicate exists”.
差不多就是这样了
And that’s pretty much it.
[打字中]
[Typing]
基本上就是我所写的这样了
So basically this is what I am doing here.
我创建了一个集合
I have my set,
然后给这个集合添加了一个值
now with this set I am adding a value.
就像我在讲义中说的一样 让我们快速回顾一下
Now as I said in my presentation if I can go back to this real quick.
讲义中差不多就是这样写的
The presentation pretty much states that
集合中的每个元素必须是唯一的
every element within the set must be unique.
如果你想加入一个重复值
So if you would, if you try to enter in a duplicate value,
是不会成功的
It won’t be allowed.
如果你加了一个重复值 集合会返回一个 false
If you try to add a duplicate value, they’re gonna get you a value of false.
就像现在这样
So this is what’s happening here.
mySet.add(x)
My set dot add x
如果这个值等于 false 那么就意味着有重复值存在
if this is equal to false, then this means that a duplicate value exists.
我们测试一下代码
So let’s test this out.
先复制这些 然后回到我们的主方法
We’re gonna copy this, go back up to our main method.
粘贴 传递这里这个数组
Paste, pass in the array here.
我们还是用相同的数组列表
we’re using the same ArrayList.
好的 我们运行一下这个程序 先来清空之前的记录
Now, we’re gonna simply just run the application. We’re gonna clean this out.
然后运行这个程序 就用我们刚写的新方法
There we’re just gonna run this applicationwith this new method that I’ve created.
好的 运行程序
Alright, so we run the application.
存在一个重复值
A duplicate exists.
我们也能把这个重复值打印出来
We can also print out the actual duplicate value
这里 这可以使结果更清楚
here. So make this a little bit more clear.
存在一个重复值
A duplicate exists.
保存 然后再运行
Save it, and run it again.
这个重复值就是 3
That is the duplicate value 3.
这个 foreach 循环的时间复杂度就是O(n)
The time complexity of this foreach loop is O of n.
好的 教程到这里就要结束了
Alright, so we’ve reached the end of the video.
如果你有任何问题 就在下面留言吧
If you have any questions, please leave them in the comments below.
如果你感觉从视频里学到了东西 别忘了给视频点赞
Don’t forget to like the video if you’ve learned some stuff from this video,
当然别忘了订阅我 我们下次见
also subscribe and until next time.

发表评论

译制信息
视频概述

用JAVA实现一个判断数组中是否存在重复值的方法

听录译者

One静茹

翻译译者

[B]刀子

审核员

审核团O

视频来源

https://www.youtube.com/watch?v=L7O1kmzPJoA

相关推荐