Java&Go-LeetCode973. 最接近原点的 K 个点-快排 | 最大堆
  • 算法
    • 1.快排
    • 2.每次寻找基准数后判断基准数是否刚好在K-1位置
      • 如果在,那么左侧刚好是最小的K个point
      • 如果不在,递归寻找
public int[][] kClosest(int[][] points, int K) {
    int left = 0, right = points.length - 1;
    int index = partition(points, left, right);
    while (index != K - 1) {
        if (index < K - 1) {
            left = index + 1;
        } else {
            right = index - 1;
        }
        index = partition(points, left, right);
    }

    int[][] result = new int[K][];
    for (int i = 0; i < K; i++) {
        result[i] = points[i];
    }
    return result;
}

private int partition(int[][] points, int start, int end) {
    int index = new Random().nextInt(end-start+1) + start;
    swap(points, index, end);
    int small = start - 1;
    for (index = start; index < end; index++) {
        if (compare(points[index], points[end]) < 0) {
            small++;
            if (small != index) {
                swap(points, small, index);
            }
        }
    }
    swap(points, ++small, end);
    return small;
}

private void swap(int[][] points, int x, int y) {
    int[] temp = points[x];
    points[x] = points[y];
    points[y] = temp;
}

private int compare(int[] x, int[] y) {
    return (x[0]*x[0]+x[1]*x[1]) - (y[0]*y[0]+y[1]*y[1]);
}
func kClosest(points [][]int, K int) [][]int {
    left, right := 0, len(points) - 1
    index := partition(points, left, right)
    for index != K - 1 {
        if index < K - 1 {
            left = index + 1
        } else {
            right = index - 1
        }
        index = partition(points, left, right)
    }

    result := make([][]int, K)
    for i := 0; i < K; i++ {
        result[i] = points[i]
    }
    return result
}

func partition(points [][]int, start, end int) int {
    rand.Seed(time.Now().Unix())
    index := rand.Intn(end-start+1) + start
    points[index], points[end] = points[end], points[index]
    small := start - 1
    for index = start; index < end; index++ {
        if compare(points[index], points[end]) < 0 {
            small++
            if small != index {
                points[index], points[small] = points[small], points[index]
            }
        }
    }
    points[small+1], points[end] = points[end], points[small+1]
    return small+1
}

func compare(point1, point2 []int) int {
    return (point1[0]*point1[0]+point1[1]*point1[1]) - (point2[0]*point2[0]+point2[1]*point2[1])
}
  • 算法
    • 1.最大堆
    • TODO
LeetCode题解 文章被收录于专栏

测试

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议