[Algorithm/Swift] Codility / OddOccurrencesInArray

문제

https://app.codility.com/programmers/lessons/2-arrays/odd_occurrences_in_array/

풀이

홀수 개의 요소가 포함된 배열이 주어집니다.

각 요소는 짝을 이루는데 짝이 없는 하나의 요소를 반환하면 됩니다.

Tip

• 중복값을 넣을수 없는 Set이지만 Count가 가능한 NSCountedSet을 사용한다.
• Performance를 위해 XOR(^) 비트 연산자를 사용한다.
  대응하는 비트가 같지 않으면 1을 반환한다.
• 비트연산자가 가장 효율과 성능이 좋다.

Code

public func solution(_ A : inout [Int]) -> Int {
    
    let countAbleSet = NSCountedSet(array: A)
    var resultNum = 0
    
    for i in A {
        if countAbleSet.count(for: i) == 1 {
            resultNum = i
        }
    }
    
	return resultNum
}

처참,,,;;;

public func solution(_ A : inout [Int]) -> Int {
    var temp = 0
        for item in A {
            temp ^= item
        }
        return temp
}

Detected time complexity: O(N) or O(N*log(N))
비트 연산자 ^를 썼는데 대응하는 비트가 같지 않으면 1을 반환한다.
값이 꼭 하나 다를 때 쓸 수 있다.

public func solution(_ A : inout [Int]) -> Int {
    var dict: [Int: Int] = [:]
        for num in A {
            dict[num] = (dict[num] ?? 0) + 1
        }

        let result = dict.keys.filter { dict[Int($0)]! % 2 != 0 }.first!
        
        return result
}

다른분꺼 참고했는데 동일한 100% 였다. 하지만 속도에서는 비트연산자가 제일 빨랐다.

public func solution(_ A : [Int]) -> Int {
    
    
//    0.0002549886703491211
//    var temp = 0
//        for item in A {
//            print("before item: \(item), temp: \(temp)")
//            temp ^= item
//            print("after item: \(item), temp: \(temp)")
//
//        }
//
//        return temp
    
    
//    0.00032401084899902344
//    let orignArray = A
//    let emptyNSData: NSCountedSet = NSCountedSet(array: orignArray)
//    var resultNum = 0
//
//    for i in orignArray {
//        if emptyNSData.count(for: i) == 1 {
//            resultNum = i
//        }
//    }
//
//    print(resultNum)
//    return resultNum
    
//    0.00037598609924316406
    var dict: [Int: Int] = [:]
        for num in A {
            dict[num] = (dict[num] ?? 0) + 1
            print(dict)
        }

        let result = dict.keys.filter { dict[Int($0)]! % 2 != 0 }.first!
        return result
    
}