Codility -3 OddOccurrencesInArray(Java)

( https://app.codility.com/programmers/lessons/2-arrays/odd_occurrences_in_array/ ) 문제링크.

 

If문으로 풀다가, 시간복잡도 측면에서도 그렇고, 이렇게 풀면 안될 것같았음. 따라서 다른사람의 풀이를 분석.

 

- XOR연산풀이.

public class OddOccurrencesInArray {
    public static void main(String[] args) {
        int[] arr = {9, 4, 9, 4, 7, 9, 9, 4, 4};
        System.out.println(solution(arr));
    }
    
    public static int solution(int[] A) {
        int answer = 0;
        for(int num : A) {
            answer ^= num; // answer = answer ^ num;  a = a + 1 == a += 1;
        }
        return answer;
    } 
}

- 윗풀이 시간복잡도

O(N) or O(N*log(N))

 

* 필요개념

- What does for (int p : ps) do?

for (int p : ps)
   counts[p]++;

 -> This is a for-each loop(enhanced for). It sets p to the first element of ps, then runs the loop body. Then it sets p to the second element of ps, then runs the loop body. And so on.

 - > ps자리에는 배열만 사용가능.

It's approximately short for:

for(int k = 0; k < ps.length; k++)
{
    int p = ps[k];
    counts[p]++;
}

 

- ^연산(XOR연산)

 -> 양쪽 비트가 서로 다른 비트면 1, 아니면 0의 결과를 낸다. (10진수로 반환한다)

 ex) 9(1001) ^ 15(1111) = 6(0110)