美文网首页
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)

    Describe a Θ(nlgn) time algorithm that, given a set S of ...

  • 124. Binary Tree Maximum Path Su

    Given a binary tree, find the maximum path sum. For this ...

  • nanomsg使用记录--java版

    1 PAIR 模式 Pair.java 2 PAIR 模式 Pair.java 3 REQREP模式 4 PUBS...

  • Weighted Median. Θ(nlgn) & Θ

    Test Driven: Solutions: The first Θ(nlgn) algorithm is de...

  • 2022-05-16

    Manhattan-based Au pair looking for an Au pair/ Mandarin ...

  • 中缀调用

    定义public infix fun A.to(that: B): Pair = Pair(this, th...

  • pair

    男女 阴阳 正负,均是成对的

  • pair

    pair是一个很实用的“小玩意”,当想要将两个元素绑在一起作为一个合成元素、又不想要因此定义结构体时,使用pair...

  • 关于排序

    基于比较排序的算法的性能是有上限的,大部分人都知道是nlgn,但是为什么多年的研究都突破不了nlgn呢,其实数学早...

  • C++11——专门标准库设备

    标准库tuple类模版 tuple是一个与pair相似的模版。每个pair类型的成员都有不同的类型,但每个pair...

网友评论

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

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