[Arrays] firstDuplicate - Google

Problem:

Given an array a that contains only numbers in the range from 1 to a.length, find the first duplicate number for which the second occurrence has the minimal index. In other words, if there are more than 1 duplicated numbers, return the number for which the second occurrence has a smaller index than the second occurrence of the other number does. If there are no such elements, return -1.

 

Example

• For a = [2, 1, 3, 5, 3, 2], the output should be firstDuplicate(a) = 3.

  There are 2 duplicates: numbers 2 and 3. The second occurrence of 3 has a smaller index than the second occurrence of 2 does, so the answer is 3.

• For a = [2, 2], the output should be firstDuplicate(a) = 2;

• For a = [2, 4, 3, 5, 1], the output should be firstDuplicate(a) = -1.

-Summary-

1. Use linear search algorithm to find a shortest duplicate index number

처음엔 이중 for loop 으로 index끼리 비교해가며 답을 찾았는데, speed limit 에 걸려 통과 못하는 케이스들이 있었다. 따라서 Linear search algorithm 으로 다시 풀었다. Set 일 경우에는 'in' method 가 O(1) 이므로 더 빨라진다.

 

모든 문제에 대한 저작권은 CodeSignal 회사에 있습니다. [Copyright © 2020 BrainFights Inc. All rights reserved]

https://codesignal.com/