[Codility] Algorithmic skills. FirstUnique

https://app.codility.com/programmers/trainings/4/first_unique/

A non-empty array A consisting of N integers is given. The unique number is the number that occurs exactly once in array A.
For example, the following array A:
A[0] = 4 A[1] = 10 A[2] = 5 A[3] = 4 A[4] = 2 A[5] = 10

contains two unique numbers (5 and 2).
You should find the first unique number in A. In other words, find the unique number with the lowest position in A.
For above example, 5 is in second position (because A[2] = 5) and 2 is in fourth position (because A[4] = 2). So, the first unique number is 5.
Write a function:
class Solution { public int solution(int[] A); }
that, given a non-empty array A of N integers, returns the first unique number in A. The function should return −1 if there are no unique numbers in A.
For example, given:
A[0] = 1 A[1] = 4 A[2] = 3 A[3] = 3 A[4] = 1 A[5] = 2

the function should return 4. There are two unique numbers (4 and 2 occur exactly once). The first one is 4 in position 1 and the second one is 2 in position 5. The function should return 4 bacause it is unique number with the lowest position.
Given array A such that:
A[0] = 6 A[1] = 4 A[2] = 4 A[3] = 6

the function should return −1. There is no unique number in A (4 and 6 occur more than once).
Write an efficient algorithm for the following assumptions:
N is an integer within the range [1..100,000];each element of array A is an integer within the range [0..1,000,000,000].

 

배열에 중복된 값이 있는지 검사하는 문제입니다.

 

어떤 자료구조를 이용할지가 가장 중요한 문제인거같네요. 저는 두 가지 방법을 생각하였습니다.

 

하나는 LinkedList 그리고 하나는 Map 입니다.

 

배열을 이용하기엔 결과 값을 저장하기 힘듭니다. 또한 문제로 주어진 N이 최대 10억까지 이므로 배열을 생성 하지 못할 거에요.

따라서 저는 두 가지 방법을 시도했고, LinkedList는 퍼포먼스 체크에서 만점을 받지 못했습니다.

 

따라서 Map을 이용하였고 결과는 Score 100% 입니다.

 

간단하게 for loop를 돌면서 Map에 값을 저장시키고, 마지막으로 갯수를 체크하는 간단한 로직입니다.

아래는 코드입니다.

 

public class FirstUnique {
    public int solution(int[] A) {
        Map<Integer, Integer> result = new HashMap<>();

        for (int i : A) {
            Integer aDefault = result.getOrDefault(i, 0);
            result.put(i, ++aDefault);
        }

        for (int i : A) {
            if (result.get(i) == 1) {
                return i;
            }
        }
        return -1;
    }
}