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