• #### 科普

SCIENCE

#### 英语

ENGLISH

#### 科技

TECHNOLOGY

MOVIE

FOOD

#### 励志

INSPIRATIONS

#### 商业

BUSINESS

#### 社会

SOCIETY

TRAVEL

#### 动物

ANIMALS

KIDS

#### 卡通

CARTOON

#### 计算机

COMPUTER

#### 心理

PSYCHOLOGY

#### 教育

EDUCATION

#### 手工

HANDCRAFTS

#### 趣闻

MYSTERIES

CAREER

GEEKS

#### 时尚

FASHION

• 精品课
• 公开课
• 欢迎下载我们在各应用市场备受好评的APP

点击下载Android最新版本

点击下载iOS最新版本

扫码下载译学馆APP

#### 编程面试题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.

Inside this array, we have six elements.

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,

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.

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,

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]

at length, j plus plus.

Now inside this nested for loop

what we want to do is add an if conditional statement.

So if that element at position i

is equal to myArray.

at position j, so right here what we are doing

So I, right here we are doing, we’re…

comparing the content of the element at position i

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

if an element at position i,

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

is equal to O of n square
Alright, now this time complexity of O n if square is not the ideal time complexity.

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.

and as I say it before, it has a time complexity of n square.

Now, what you want to do is actually use a for loop.

This for loop is gonna have a time complexity of n or a linear time complexity.

So we want to use a for loop,

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

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.

We want to create ourselves a foreach loop.

And basically what we want to do is this.

We wanna say if, or for, we wanna say for

every integer that’s in my array.
［打字中］
[Typing]

We want to add an if conditional that states if
［打字中］
[Typing]

my set. add x
［打字中］
[Typing]

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.

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

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.

That is the duplicate value 3.

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.

##### 译制信息

One静茹

[B]刀子

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