Try   HackMD
tags: ADA 4.3 Closest Pair of Points

ADA 4.3: Closest Pair of Points 最近點對

經典問題： 最近點對

Define Closest Pair of Points

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More → 

兩個以上的點 座標範圍皆定義於第一象限(+,+)

輸出為最距離最接近的兩個點 aka smallest d(Pi,Pj)

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Resolve

1D

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More → 

簡化問題 降維思考

2D

  • Divide-and-Conquer
    Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →
  • Algo with Cross-Regions case
    Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More → 
如上面的Case 如果目前L-min = 10 R-min = 13
我們其實只要從中線往左右去找10的距離去檢查點就可以了

What if 所有的點都在 δ 範圍內

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More → 

​已經限縮了X軸在2δ 範圍
​從Y軸來考慮 我們要找的答案如果希望<δ 那他們必定在同一個δ的範圍內

What if 所有的點都在 δX2δ 範圍內

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More → 

由前面的δ去定義 一個block內不可能會出現第二個點
複雜度由n/2*n/2下降到8

Closet case in Cross-Regions Scope

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Algorithm Complexity

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More → 

​定義BaseCase
​先sort X 才能切開
​找出左右兩側最靠近的Pair
​
​開始解析Cross-Regions Case
​將不在範圍內的點去除
​依照Ｙ軸排序
​計算每一個點對於自身距離與其他8個block的距離

Algorithm Preprocessing

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Other Algorithm

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More → 

具備能夠將問題簡化然後解決的性質
能夠重新利用已經回傳的答案並Combined
要去檢視複雜度的重要性 -> 真的比暴力解省時間嗎
Last changed by 
 
30讀書會
一群超過30歲，卻努力不懈的人
0
730

Read more

Modular Mojo 讀書會

階段一：閱讀官方文件

May 2, 2024
Week10 (May 20)

260. Single Number III Question Given an integer array &lt;mark&gt;nums&lt;/mark&gt;, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order. You must write an algorithm that runs in linear runtime complexity and uses only constant extra space. Hand in homework before Saturday. :::success Roger的作業 xander的作業

Jun 14, 2023
ADA 1.1 Introduction

Why we care? 算力不是免費的。 本課程作業速度不到標準，也會被退件。 名詞定義 Definition 1. Problem 問題 會有明確的Input與Output Ex. 冠軍問題

Jun 2, 2023
leetcode刷題讀書會行前須知

使用markdown 協作筆記

May 31, 2023
Read more from 30讀書會
Published on HackMD