Lesson 2 - OddOccurrencesInArray

A non-empty array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired.

For example, in array A such that:

A[0] = 9 A[1] = 3 A[2] = 9
A[3] = 3 A[4] = 9 A[5] = 7
A[6] = 9
the elements at indexes 0 and 2 have value 9,
the elements at indexes 1 and 3 have value 3,
the elements at indexes 4 and 6 have value 9,
the element at index 5 has value 7 and is unpaired.
Write a function:

class Solution { public int solution(int[] A); }

that, given an array A consisting of N integers fulfilling the above conditions, returns the value of the unpaired element.

For example, given array A such that:

A[0] = 9 A[1] = 3 A[2] = 9
A[3] = 3 A[4] = 9 A[5] = 7
A[6] = 9
the function should return 7, as explained in the example above.

Write an efficient algorithm for the following assumptions:

N is an odd integer within the range [1..1,000,000];
each element of array A is an integer within the range [1..1,000,000,000];
all but one of the values in A occur an even number of times.

---

배열에서 같은 숫자가 아닌 다른 숫자가 있는지 찾는 문제이다. filterNot을 구현하면 되는 문제이다. 익숙하지 않아서 그런지 어렵다 ㅠㅠ

퍼포먼스 및 사례 simple1에서 실패했다. 퍼포먼스는 예상했는데 simple1은 어디일까
퍼포먼스에서 좀 더 나은 점수를 받기 위해, 같은 인덱스 비교는 필요 없으므로 continue 시키고, 같은 값을 찾으면 break 시켰다.

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
import java.util.Arrays;

class Solution {
    public int solution(int[] A) {
        if (A.length == 1) return A[0];

        int result = 0;
        Arrays.sort(A);
        
        for(int i=0; i<A.length; i++) {
            boolean isPaired = false;            
            for(int j=0; j<A.length; j++) {
                // if same value pass
                if(i == j) {
                    continue;
                }

                if(A[i] == A[j]) {
                    isPaired = true;
                    continue;
                }
            }

            if(!isPaired) {
                result = A[i];
                break;
            }
        }        

        return result;        
    }
}

사실 이중루프를 쓰면 시간복잡도에서 O(N)²이 되는 문제는 진작 알고 있었다.. 이거 O(N) 으로 풀 수 있나?

---

자료구조를 활용한 방안

인터넷을 찾아보니 Set으로 푸신 분들도 있다.

class Solution {
	public int solution(int[] A) {
    	Set<Integer> set = new HashSet<>();
        
        for(int i : A) {
        	if(set.contains(i)){
            	set.remove(i);
            } else {
            	set.add(i);
            }
        }
        
        return set.iterator().next();
    }
}

HashMap에 key value로 count추가해서 넣으신분도 있다.

class Solution {
    public int solution(int[] A) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < A.length; i++) {
            if (map.get(A[i]) == null) { // 맵에 없으면 1로 put 
                map.put(A[i], 1);
            } else { // 맵에 있으면 기존값에 +1
                map.put(A[i], map.get(A[i])+1);
            }
        }
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            // 2로 나눈 나머지가 1인 경우
            if (entry.getValue() % 2 == 1) {
                return entry.getKey();
            }
        }
        return 0;
    }
}

---

베스트 답안

비트 연산을 활용한 답이 있다.

계산 결과는 다음을 참조하자.

그러면 O(N) or O(N*log(N)) 롤 풀 수 있다.

XOR 연산으로 대응되는 두 비트가 서로 다르면 1을 반환하고, 서로 같으면 0을 반환한다.

XOR연산을 하다보면 같은 수는 0이 되고 다른 수는 1이 되면서 계속하다보면 결국 같은 수가 한 번 더 나오지 않은 수가 남는다고 한다. (이걸 어떻게 알아)

class Solution {
	public int solution(int[] A) {
    	int answer = 0;
        for (int num : A) {
        	answer ^= num;
        }
        
        return answer;
    }
}