查找x个最接近目标的数组元素
查找x个最接近目标的数组元素
提问于 2018-06-02 03:18:01
我有一个可能包含1000+元素的数组，并且有一个动态目标数，我希望获得与目标数最接近的x个元素数。示例：
let targetNumber = 1000.0
let matches = 5
let array = [1000,2000,3000,4000,5000,6000,7000,8000,9000,10000,11000,12000,13000,14000,15000,16000,17000]如果x是5，我需要像下面这样过滤结果：[1000,2000,3000,4000,5000,6000]
如果目标数是10000，我需要从根本上颠倒结果，[10000,9000,8000,7000,6000,5000]
数组可以排序，也可以不排序。使用Swift实现此结果的最佳且最有效的方法是什么？
回答 2
Stack Overflow用户
回答已采纳
发布于 2018-06-02 05:18:19
让我们定义一些测试数据。让我们有一个函数：
func getClosest(count: Int, from values: [Int], to targetNumber: Int) -> [Int]我们将使用以下内容进行测试：
let array = [1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000, 10000, 11000, 12000, 13000, 14000, 15000, 16000, 17000]
print(getClosest(count: 5, from: array, to: 1000))
print(getClosest(count: 5, from: array, to: 10000))一个简单的实现是根据到目标数字的距离对数组进行排序，并获取前X个值：
func getClosest(count: Int, from values: [Int], to targetNumber: Int) -> [Int] {
let getDistance: (Int) -> Int = {
return abs(targetNumber - $0)
}
return Array(
values
.sorted { getDistance($0) < getDistance($1) }
.prefix(count)
)
}性能不会很差(O(n * log(n))复杂性，排序的复杂性)，但它不是最优的。
要真正获得良好的复杂性，我们需要使用一种称为Priority Queue的专用数据结构。优先级队列是存储元素的抽象数据结构的名称，它总是可以返回优先级最低的元素。
这种结构的一个简单实现是：
struct PriorityQueue<Element, Priority: Comparable> {
private var elements: [(element: Element, priority: Priority)] = []
var isEmpty: Bool {
return elements.isEmpty
}
var count: Int {
return elements.count
}
mutating func insert(element: Element, priority: Priority) {
elements.append((element: element, priority: priority))
elements.sort { $0.priority < $1.priority }
}
mutating func peek() -> Element? {
return elements.first?.element
}
mutating func pop() -> Element? {
guard !isEmpty else {
return nil
}
return elements.remove(at: 0).element
}
func getElements() -> [Element] {
return Array(elements.map { $0.element })
}
}这基本上只是对内部数组进行排序，但请注意优先级队列的接口是什么样子的。
然后我们可以这样实现我们的函数：
func getClosest(count: Int, from values: [Int], to targetNumber: Int) -> [Int] {
let getDistance: (Int) -> Int = {
return abs(targetNumber - $0)
}
var queue = PriorityQueue<Int, Int>()
for value in values {
queue.insert(element: value, priority: -getDistance(value))
if queue.count > count {
_ = queue.pop()
}
}
return queue.getElements()
}现在，通过一个简单的优先级队列实现，这根本不会增加复杂性，但是如果我们更好地实现优先级队列，那么它就会工作。
优先级队列通常使用Heap实现，或者更具体地说，使用Fibonacci heap实现。
一旦你理解了算法，实现它们并不复杂，但是已经有一些实现了。有关示例，请参阅Swift Algorithm Club: Heap and Priority Queue Data Structure。
Stack Overflow用户
发布于 2018-06-02 04:22:34
尝尝这个,
let closestToTarget = array.filter { array.index(of: $0)! <= array.index(of: targetNumber)! && array.index(of: targetNumber)! - array.index(of: $0)! <= 5 }.reversed() as [Int]页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/50649823
复制相关文章
相似问题