摘要:前言的最接近原點的個點我們有一個由平面上的點組成的列表。這里,平面上兩點之間的距離是歐幾里德距離。提示解題思路本題首先要知道什么是歐幾里德距離。歐幾里德距離又叫做歐幾里德度量,指的是是歐幾里得空間中兩點間普通即直線距離。
前言
Weekly Contest 119的 最接近原點的 K 個點:
解題思路我們有一個由平面上的點組成的列表 points。需要從中找出 K 個距離原點 (0, 0) 最近的點。
(這里,平面上兩點之間的距離是歐幾里德距離。)
你可以按任何順序返回答案。除了點坐標的順序之外,答案確保是唯一的。
示例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 <= 10000
-10000 < points[i][0] < 10000
-10000 < points[i][3] < 10000
本題首先要知道什么是歐幾里德距離。歐幾里德距離又叫做歐幾里德度量,指的是是歐幾里得空間中兩點間“普通”(即直線)距離。只是說概念大家很難理解,先用本題需要用到的二維空間中計算歐幾里德距離的數學公式就能很好理解了:
已知原點坐標為(0,0),存在兩個點A(x1,y1)和B(x2,y2),則點A和B的歐幾里德距離則為
$$ sqrt{(x_1-x_2)^2+(y_1-y_2)^2} $$
而點A到原點的歐幾里德距離則為
$$ sqrt{x_1^2+y_1^2} $$
然后利用這個公式可以計算出每個點到原點的歐幾里德距離,之后只需要找出最近的幾個點即可。
此處需要注意題目中的
除了點坐標的順序之外,答案確保是唯一的
這說明每個點到原點的舉例應該都是不同的。
實現代碼/** * 973. 最接近原點的 K 個點 * 某個點到原點的歐幾里德距離為坐標值的平方之和開根號即可 * @param points * @param K * @return */ public int[][] kClosest(int[][] points, int K) { //根據題目意思,每個點到原點的歐幾里德距離都不同,可以用距離作為key //Map選擇TreeMap是因為TreeMap的key是有序(從小到大) Mapmap=new TreeMap<>(); for (int i=0;i > it=map.entrySet().iterator(); //當前遍歷到第幾個元素,用于控制點的個數 int index=0; while (it.hasNext()){ int[] point=it.next().getValue(); result[index]=point; if(index+1==K){ break; }else{ ++index; } } return result; }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/72982.html
摘要:題目鏈接題目分析給一個坐標數組,從中返回個離最近的坐標。其中,用歐幾里得距離計算。思路把距離作為數組的鍵,把對應坐標作為數組的值。用函數排序,再用函數獲取前個即可。最終代碼若覺得本文章對你有用,歡迎用愛發電資助。 973. K Closest Points to Origin 題目鏈接 973. K Closest Points to Origin 題目分析 給一個坐標數組points...
摘要:而代碼是給出現情況增加次數,出現一次排序導入運算符模塊的方法,按照第二個元素的次序對元組進行排序,此處的排序為逆序。 機器學習——K近鄰算法 概述 k近鄰是一種基本分類與回歸方法. 輸入:特征向量 輸出:實例的類別(可取多類) 核心思想:如果一個樣本在特征空間中的k個最相鄰的樣本中的大多數屬于某一個類別,則該樣本也屬于這個類別,并具有這個類別上樣本的特性. 優點:計算精度高、對異常值...
閱讀 3228·2021-11-15 11:37
閱讀 2449·2021-09-29 09:48
閱讀 3813·2021-09-22 15:55
閱讀 3014·2021-09-22 10:02
閱讀 2636·2021-08-25 09:40
閱讀 3225·2021-08-03 14:03
閱讀 1691·2019-08-29 13:11
閱讀 1570·2019-08-29 12:49