美文网首页
Pair of Sum. Θ(nlgn)

Pair of Sum. Θ(nlgn)

作者: R0b1n_L33 | 来源:发表于2017-09-21 08:27 被阅读23次

    Describe a Θ(nlgn) time algorithm that, given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose sum is exactly x.

    func pairOf(sum:Int, in array:inout [Int]) throws -> (Int, Int)? {
        guard array.count>1 else { throw TestError.argumentFault }
        mergeSort(array: &array)
        var low = 0, high = array.count-1
        while low != high {
            var currentSum = array[low] + array[high]
            if currentSum > sum { high -= 1 }
            else if currentSum < sum { low += 1 }
            else { return (array[low], array[high]) }
        }
        return nil
    }
    
    var s = try Int.randomArray()
    let sum = try Int.random()
    try pairOf(sum: sum, in: &s)
    

    相关文章

      网友评论

          本文标题:Pair of Sum. Θ(nlgn)

          本文链接:https://www.haomeiwen.com/subject/wxtzsxtx.html