0973-最接近原点的K个点

题目描述

https://leetcode.cn/problems/k-closest-points-to-origin

给定一个数组 points，其中points[i] = [xi, yi]表示 X-Y 平面上的一个点，并且是一个整数 k ，返回离原点 (0,0) 最近的 k 个点。

这里，平面上两点之间的距离是欧几里德距离（√(x1- x2)2+ (y1- y2)2）。

你可以按任何顺序返回答案。除了点坐标的顺序之外，答案确保是唯一的。

示例 1：

输入：points = [[1,3],[-2,2]], k = 1

输出：[[-2,2]]
解释： 
(1, 3) 和原点之间的距离为 sqrt(10)，
(-2, 2) 和原点之间的距离为 sqrt(8)，
由于 sqrt(8) < sqrt(10)，(-2, 2) 离原点更近。
我们只需要距离原点最近的 K = 1 个点，所以答案就是 [[-2,2]]。

示例 2：

输入：points = [[3,3],[5,-1],[-2,4]], k = 2
输出：[[3,3],[-2,4]]
（答案 [[-2,4],[3,3]] 也会被接受。）

提示：

1 <= k <= points.length <= 10^4
-10^4 < xi, yi < 10^4

思路

使用二维数组记录长度的平方和索引，将结果排序后输出前k个。

csharp

public class Solution {
    public int[][] KClosest(int[][] points, int k) {

        //使用二维数组记录长度的平方和索引
        int[][] arr = new int[points.Length][];
        for(int i=0; i<arr.Length; i++){
            arr[i] = new int[2];
            int distance2 = points[i][0] * points[i][0] + points[i][1] * points[i][1];
            arr[i][0] = distance2;
            arr[i][1] = i;
        }
    	Array.Sort(arr,( a, b)=>{
    		if(a[0] > b[0]){
    			return 1;
    		}
    		if(a[0] < b[0]){
    			return -1;
    		}
    		return 0;
    	});

        //输出 array
        for(int i=0; i<arr.Length; i++){
            Console.WriteLine("{0} {1}",arr[i][0], arr[i][1]);
        }

    	//输出
    	int[][] result = new int[k][];
    	for(int i=0; i<k; i++){
            result[i] = new int[2];
            int index = arr[i][1];
    		result[i][0] = points[index][0];
    		result[i][1] = points[index][1];
    	}
    	return result;
    }
}

0973-最接近原点的K个点 #

题目描述 #

思路 #

0973-最接近原点的K个点

题目描述

思路