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 
}

CodePudding user response：

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.