英文:
how to calculate the best params for my algorithm？
问题
以下是您提供的代码的翻译：
func kClosest(points [][]int, k int) [][]int {
res := make([][]int, 0, k)
max := 0
for i, v := range points {
p := v[0]*v[0] + v[1]*v[1]
if len(res) < k {
if p > max {
max = p
}
res = append(res, v)
if i == k-1 {
sort.Slice(res, func(i, j int) bool {
return res[i][0]*res[i][0]+res[i][1]*res[i][1] < res[j][0]*res[j][0]+res[j][1]*res[j][1]
})
}
continue
}
if p > max {
continue
}
res = append(res, v)
// 50是我想要优化的参数
if len(res) > 50*k {
sort.Slice(res, func(i, j int) bool {
return res[i][0]*res[i][0]+res[i][1]*res[i][1] < res[j][0]*res[j][0]+res[j][1]*res[j][1]
})
res = res[:k]
max = res[k-1][0]*res[k-1][0] + res[k-1][1]*res[k-1][1]
}
}
sort.Slice(res, func(i, j int) bool {
return res[i][0]*res[i][0]+res[i][1]*res[i][1] < res[j][0]*res[j][0]+res[j][1]*res[j][1]
})
res = res[:k]
return res
}
请注意，我只翻译了您提供的代码部分，其他内容不包括在内。
英文:
<https://leetcode.com/problems/k-closest-points-to-origin>
when I try to solve this leecode problem, I am curious about how to get the best parameters in my algorithm.
runtime
[1]: https://i.stack.imgur.com/enVe3.png
here is my code:
func kClosest(points [][]int, k int) [][]int {
res := make([][]int,0,k)
max := 0
for i,v := range points {
p := v[0]*v[0]+v[1]*v[1]
if len(res) <k {
if p > max {
max = p
}
res = append(res,v)
if i == k-1 {
sort.Slice(res,func(i,j int) bool {
return res[i][0]*res[i][0]+res[i][1]*res[i][1] < res[j][0]*res[j][0]+res[j][1]*res[j][1]
})
}
continue
}
if p > max {
continue
}
res = append(res,v)
// the 50 is the parameters I want to optimal
if len(res) > 50*k {
sort.Slice(res,func(i,j int) bool {
return res[i][0]*res[i][0]+res[i][1]*res[i][1] < res[j][0]*res[j][0]+res[j][1]*res[j][1]
})
res = res[:k]
max = res[k-1][0]*res[k-1][0]+res[k-1][1]*res[k-1][1]
}
}
sort.Slice(res,func(i,j int) bool {
return res[i][0]*res[i][0]+res[i][1]*res[i][1] < res[j][0]*res[j][0]+res[j][1]*res[j][1]
})
res = res[:k]
return res
}
答案1
得分: 0
我认为你正在使用的算法基本上是错误的 - 你重复对切片进行排序并在其长度过长时截断它，以尝试避免O(n log n)的运行时间。这样会导致整体性能为O(n log k)（每次排序的复杂度为O(k log k)，并且大约需要对切片进行 n/k 次排序）。你可以通过使用最大堆来更容易地实现O(n log k)的性能，每次插入一个元素到堆中（当堆的大小已经达到 k 且新元素小于最大值时，先移除最大值）。
但是最好的方法是使用快速选择（QuickSelect）来选择最小的 k 个元素。它的时间复杂度为O(n)，而且显然这个问题是针对这种解决方案的，因为它不要求答案按任何特定顺序排列。虽然它不在标准库中，但如果你无法自己编写，你可以很容易在网上找到实现。作为优化的一种方式，可能最好的是预先计算一个向量长度的切片，并将其与原始切片的索引关联起来，然后对该切片进行快速选择，但这需要进行性能分析才能确定。
英文:
I think you're using the essentially wrong algorithm -- you're repeatedly sorting the slice and truncating it when it gets too long to try to avoid the O(n log n) runtime. This gives you O(n log k) performance overall (each sort is O(k log k), and you sort approximately n/k times). You can more easily get O(n log k) performance by having a max-heap to which you insert elements one by one (removing the max beforehand when the heap is already at size k and the new element is smaller than the max).
But best is use QuickSelect to select the smallest k elements. It's O(n) time, and the question is obviously geared towards this as a solution because it doesn't require the answer to be in any particular order. It's not in the standard library, but you can easily find implementations online if you can't write it yourself. As a matter of optimization, it's probably better to precompute a slice of the vector lengths coupled with indexes into the original slice and quickselect that rather than the original slice, but it's hard to know without profiling.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论