Task description

• Notice : Write an efficient algorithm O(N), O(NlogN)

Solution

First, since the length of array A can be up to 1,000,000, I use a dictionary to solve this problem. I iterate through each element of A and append it to the dictionary in the format [number: count].

After that, by iterating through the dictionary's keys and values, I find if there is any key that is not an even number.

import Foundation
import Glibc

// you can write to stdout for debugging purposes, e.g.
// print("this is a debug message")

public func solution(_ A : inout [Int]) -> Int {
    // used for check pair
    var dict: [Int:Int] = [:]

    // return value
    var rst = 0

    for item in A {
        if dict[item] == nil {
            dict[item] = 1
        } else {
            dict[item]! += 1
        }
    }

    for (k,i) in dict {
        if i % 2 != 0 {
            rst = k
            break
        }
    }
    return rst
}