LeetCode #973 K Closest Points to Origin: หมี เพนกวิน จิ้งจอก ลิง ชิงจุดใกล้สุด

LeetCode #973 K Closest Points to Origin ให้รายการจุด [x, y] กับจำนวน k แล้วให้เราเลือกจุดที่อยู่ใกล้ (0, 0) ที่สุดมาให้ครบ k จุดครับ ระยะวัดแบบเส้นตรง และส่งคำตอบกลับมาในลำดับใดก็ได้ ถ้าหลายจุดห่างเท่ากันตรงเส้นแบ่ง เลือกจุดไหนในกลุ่มนั้นก็ได้ ขอให้จำนวนครบและไม่หยิบจุดไกลกว่ามาแทนจุดใกล้กว่า

ใช้กับแอปหาร้านกาแฟหรือวินมอเตอร์ไซค์ใกล้เรา 3 แห่ง โดยตั้งเราเป็นจุดกำเนิดและใช้พิกัดบนระนาบ

points = [[1, 3], [-2, 2]], k = 1
ระยะยกกำลังสอง: 10, 8
input → output: [[1, 3], [-2, 2]], 1 → [[-2, 2]]

วันนี้หมีพี่เรียง เพนกวินถังจิ๋ว จิ้งจอกไวไว และลิงสุ่มซน จะมาเถียงกัน โดยมี บารอน สิงโตทะเลสวมโค้ตเป็นกรรมการครับ

ผู้เข้าแข่งขัน

ตัวละคร	วิธี	นิสัยที่เข้ากับวิธี
หมี “พี่เรียง”	เรียงทั้งหมดด้วย sorted	เจ้าระเบียบ ต้องเห็นทั้งแถวเรียบร้อยก่อน
เพนกวิน “ถังจิ๋ว”	max-heap ขนาด k	ประหยัดพื้นที่ หวงถังใบเล็ก
จิ้งจอก “ไวไว”	heapq.nsmallest	คล่องมือ ชอบใช้เครื่องมือที่มีอยู่แล้ว
ลิง “สุ่มซน”	quickselect สุ่มจุดแบ่ง	ใจไว ชอบแบ่งงานแล้วทิ้งกองที่ไม่จำเป็น
บารอน สิงโตทะเลสวมโค้ต	กรรมการ	ฟังเหตุผล แล้วดูเวลาที่วัดได้จริง

ก่อนเริ่ม ผมขอตั้งคะแนนเดียวให้ทุกตัวคือ x*x + y*y หรือระยะยกกำลังสอง ไม่ต้องถอดราก เพราะจำนวนไม่ติดลบเรียงก่อนและหลังถอดรากได้เหมือนกัน จุด [-2, 2] จึงได้คะแนน 8 พิกัดลบใช้ได้เพราะคูณตัวเองแล้วเป็นบวก

ให้ n คือจำนวนจุดทั้งหมด ส่วน k คือจำนวนที่ต้องคืน O(n) หมายถึงงานโตตามจำนวนจุด ไม่ใช่เวลาหน่วยวินาที ส่วน log n คือจำนวนชั้นที่โตช้าจากการแบ่งกองซ้ำ ๆ ใช้เทียบแนวโน้ม แล้วดู benchmark ประกอบ

วิธีที่ 1: หมีพี่เรียง — เรียงทั้งหมดด้วย sorted

“จัดทุกคนเข้าแถว เดี๋ยวก็รู้ว่าใครใกล้” พี่เรียงกางไม้บรรทัดแล้วเรียก sorted โดยให้คะแนนระยะเป็นกุญแจเรียง จากนั้นหยิบ k จุดแรก วิธีนี้อ่านตามได้ตรง ๆ และผลลัพธ์เรียงจากใกล้ไปไกลให้ด้วย แม้โจทย์ไม่ได้บังคับ

เวลา: O(n log n) โดยทั่วไป บวกการหยิบผล O(k); การเรียงของ Python ใช้ประโยชน์จากข้อมูลที่เรียงอยู่บางส่วนได้
หน่วยความจำเพิ่ม: O(n) สำหรับรายการใหม่และงานเรียง รวมผลลัพธ์แล้วยังอยู่ระดับนี้
ข้อดี: โค้ดสั้น ตรวจง่าย ผลเรียงแล้ว เหมาะเป็นคำตอบอ้างอิงในเทสต์
ข้อเสีย/edge cases: ต้องเห็นข้อมูลทั้งหมด และเสียงานเรียงจุดที่ไม่ได้ใช้เมื่อ k เล็กมาก; ระยะเท่ากันไม่จำเป็นต้องเรียงพิกัดต่อ

วิธีที่ 2: เพนกวินถังจิ๋ว — max-heap ขนาด k

“เอามาทั้งแถวทำไม ถังฉันรับแค่คนใกล้!” ถังจิ๋วใช้ heap หรือโครงสร้างที่เก็บสมาชิกให้หยิบตัวหัวแถวได้เร็ว โดยไม่ต้องเรียงทั้งกอง ทุกครั้งที่จุดใหม่เข้ามา จะเทียบกับจุดไกลที่สุดในถัง ถ้าใกล้กว่าจึงแทนที่ มิฉะนั้นปล่อยผ่าน

เราอยากได้ max-heap ซึ่งวางคะแนนมากสุดไว้บนหัว แต่โค้ดนี้ใช้รูปแบบ min-heap ของ โมดูล heapq ที่วางค่าน้อยสุดไว้ก่อน จึงเก็บคะแนนติดลบแทน เช่น ระยะ 25 กลายเป็น -25 และขึ้นมาอยู่ก่อนระยะ 8 ที่เก็บเป็น -8 ถังเต็มเมื่อไร หัวถังคือคนที่ควรถูกพิจารณาให้ออกก่อน

k = 2, คะแนนที่เข้ามา: 10 → 8 → 1
ถังตามคะแนนจริง: [10] → [10, 8] → [8, 1]
จุดคะแนน 1 มาแทน 10; หัวถังยังเป็นคะแนนมากที่สุด

ใน heap เก็บ (-คะแนน, ลำดับที่เข้ามา, จุด) ใช้ลำดับแก้คะแนนเสมอ และเรียก heapreplace เมื่อจุดใหม่ใกล้กว่าเท่านั้น

เวลา: O(n log k) เมื่อ k >= 2; ถ้า k = 1 เป็น O(n) เพราะถังมีช่องเดียว
หน่วยความจำเพิ่ม: O(k) เก็บเฉพาะผู้เข้ารอบ ไม่รวมข้อมูลต้นทางที่ผู้เรียกถืออยู่
ข้อดี: รับข้อมูลไหลมาเรื่อย ๆ ได้ ไม่ต้องรู้จำนวนทั้งหมดก่อน แค่รู้ k
ข้อเสีย/edge cases: คำตอบยังไม่เรียง และถ้า k ใหญ่ก็ต้องดูแลถังใหญ่; โค้ดต้องกัน k = 0 ก่อนเข้าถึงหัวถัง

วิธีที่ 3: จิ้งจอกไวไว — heapq.nsmallest

“ผมขอยกงานคัดตัวให้เครื่องมือ” ไวไวชี้ไปที่ heapq.nsmallest(k, points, key=distance2) ซึ่งสื่อความหมายว่าขอสมาชิกเล็กสุด k ตัวตามคะแนน ระยะที่ใช้ยังเป็นสูตรเดิม แต่ไม่ต้องเขียนขั้นตอนดูแลถังเอง และได้คำตอบเรียงตามคะแนนด้วย

ความต่างจากเพนกวินคือเราเรียกตัวช่วยแบบเลือกกลยุทธ์ให้ ใน CPython ที่ใช้วัด เมื่อ k = 1 มันใช้ทางลัดหาค่าน้อยสุด และเมื่อ k ไม่น้อยกว่าความยาวข้อมูลที่รู้ได้ มันเลือกเรียงทั้งหมด ส่วนกรณีทั่วไปใช้ถังผู้เข้ารอบแล้วเรียงถังตอนท้าย ดังนั้นตัวนี้มีญาติกับ heap ไม่ใช่อัลกอริทึมลึกลับตัวใหม่

เวลา: โดยทั่วไป O(n log k + k log k) สำหรับ 1 < k < n; k = 1 เป็น O(n) และเมื่อ k >= n กับลิสต์ ใช้การเรียง O(n log n)
หน่วยความจำเพิ่ม: O(k) สำหรับกรณีเลือกบางส่วน; เมื่อขอครบทุกจุดเป็น O(n)
ข้อดี: อ่านเจตนาออกทันที รับตัววนอ่านข้อมูลได้ และคืนผลที่เรียงแล้ว
ข้อเสีย/edge cases: ไม่ได้เก็บสถานะให้เราเติมจุดทีละรอบระหว่างโปรแกรมทำงาน; ถ้ารับสตรีมไม่สิ้นสุดก็จะรอจนจบ และเมื่อ k กินสัดส่วนมากของ n อาจแพ้การเรียงตรง ๆ

วิธีที่ 4: ลิงสุ่มซน — quickselect แบ่งสามกอง

“ไม่ต้องจัดทุกคน แค่หาเส้นแบ่งให้เจอ” สุ่มซนใช้ quickselect คือเลือกคะแนนหลักหนึ่งตัว แล้วแบ่งข้อมูลเป็นกองคะแนนน้อยกว่า เท่ากัน และมากกว่า ถ้าอันดับที่ต้องการอยู่กองซ้าย ก็ทำต่อเฉพาะซ้าย ถ้าอยู่ขวาก็ทำต่อเฉพาะขวา พออันดับที่ k - 1 อยู่ในกองเท่ากัน เราหยิบสมาชิก k ตัวแรกได้เลย

คะแนนหลัก = 8
[คะแนน < 8] | [คะแนน = 8] | [คะแนน > 8]
             ↑ ถ้าเส้นแบ่ง k ตกในกองนี้ ก็หยุดได้

การแบ่งสามกองช่วยข้ามกลุ่มระยะเท่ากันได้รวดเดียว คะแนนหลักสุ่มด้วย โมดูล random ในโค้ดนี้ใช้ตัวสุ่มแยกและ seed 973 เพื่อให้รันซ้ำแล้วได้เส้นทางเดิม ไม่ไปรบกวนสถานะสุ่มของส่วนอื่น

คำว่า in-place คือสลับตำแหน่งในพื้นที่รายการเดิมเป็นหลัก แต่เวอร์ชันนี้คัดลอกลิสต์ก่อนแบ่ง เพื่อรักษาลำดับอินพุต จึงห้ามโฆษณาว่ากินพื้นที่เพิ่มคงที่ ตัว seed ที่ตรึงไว้ทำให้เทียบซ้ำสะดวก แต่ไม่ได้รับประกันเวลาทุกอินพุต; คำว่าเฉลี่ยด้านล่างอาศัยการสุ่ม pivot ที่กระจายเหมาะสม

เวลา: เฉลี่ย O(n) แต่แย่สุด O(n²) ถ้าเลือกคะแนนหลักแล้วเหลืองานเกือบทั้งกองซ้ำ ๆ
หน่วยความจำเพิ่ม: O(n) ในโค้ดนี้เพราะคัดลอกลิสต์; ตัวแบ่งใช้ตัวแปรไม่กี่ตัวและไม่มีการเรียกตัวเองซ้อน
ข้อดี: ไม่เสียงานเรียงสมาชิกภายในกลุ่ม เหมาะอธิบายความต่างระหว่าง “เลือก” กับ “เรียง”
ข้อเสีย/edge cases: โค้ดยาว สลับพลาดง่าย ผลไม่เรียง; k = n คืนสำเนาได้ทันที และต้องแยก k = 0 ก่อนหาตำแหน่งเป้าหมาย

โค้ดทุกวิธี พร้อมเทสต์

ทุกฟังก์ชันรับ 0 <= k <= len(points) และจุดพิกัดจำนวนเต็ม โดยไม่เปลี่ยนลิสต์ต้นทาง โจทย์จริงให้ k เป็นบวกและมีจุดเสมอ แต่ผมขยายให้รับลิสต์ว่างกับ k = 0 เพื่อใช้และทดสอบสะดวก ส่วน k ติดลบหรือเกินจำนวนจุดอยู่นอกข้อตกลงนี้

เทสต์เทียบคะแนนที่เรียงแล้ว และหยิบจุดออกจากสำเนาอินพุตทีละตัว จึงตรวจจำนวนจุดซ้ำและยอมรับจุดต่างกันที่เสมอตรงเส้นแบ่งได้ ไม่ใช้ set เพราะจะทำจุดซ้ำหาย บันทึกบล็อกนี้เป็นไฟล์แล้วรันด้วย python3 -I -B file.py ได้เลย

import heapq
import random
import unittest


def distance2(point):
    x, y = point
    return x * x + y * y


def bear_sort(points, k):
    return sorted(points, key=distance2)[:k]


def penguin_heap(points, k):
    if k == 0:
        return []
    heap = []
    for i, point in enumerate(points):
        entry = (-distance2(point), i, point)
        if len(heap) < k:
            heapq.heappush(heap, entry)
        elif entry[0] > heap[0][0]:
            heapq.heapreplace(heap, entry)
    return [entry[2] for entry in heap]


def fox_nsmallest(points, k):
    return heapq.nsmallest(k, points, key=distance2)


def monkey_select(points, k):
    if k == 0:
        return []
    if k == len(points):
        return list(points)
    items = list(points)
    rng = random.Random(973)
    lo, hi = 0, len(items) - 1
    target = k - 1
    while lo <= hi:
        pivot = distance2(items[rng.randrange(lo, hi + 1)])
        lt, i, gt = lo, lo, hi
        while i <= gt:
            value = distance2(items[i])
            if value < pivot:
                items[lt], items[i] = items[i], items[lt]
                lt += 1
                i += 1
            elif value > pivot:
                items[i], items[gt] = items[gt], items[i]
                gt -= 1
            else:
                i += 1
        if target < lt:
            hi = lt - 1
        elif target > gt:
            lo = gt + 1
        else:
            break
    return items[:k]


ALL = [bear_sort, penguin_heap, fox_nsmallest, monkey_select]


class TestClosest(unittest.TestCase):
    def check_all(self, points, k):
        expected = sorted(map(distance2, points))[:k]
        for solve in ALL:
            with self.subTest(method=solve.__name__, points=points, k=k):
                before = [p[:] for p in points]
                result = solve(points, k)
                self.assertEqual(len(result), k)
                self.assertEqual(sorted(map(distance2, result)), expected)
                remaining = [tuple(p) for p in points]
                for point in result:
                    self.assertIn(tuple(point), remaining)
                    remaining.remove(tuple(point))
                self.assertEqual(points, before)

    def test_examples_and_edges(self):
        cases = [
            ([[1, 3], [-2, 2]], 1),
            ([[3, 3], [5, -1], [-2, 4]], 2),
            ([], 0),
            ([[0, 0]], 1),
            ([[7, -3]], 0),
            ([[-4, -3], [-1, -1], [0, 0], [2, -1]], 2),
            ([[1, 1], [1, 1], [2, 2]], 2),
            ([[1, 0], [0, 1], [-1, 0], [0, -1]], 2),
            ([[2, 3], [-2, -3], [0, 0]], 3),
            ([[0, 0]] * 40, 17),
        ]
        for points, k in cases:
            self.check_all(points, k)

    def test_seeded_cases(self):
        rng = random.Random(42)
        for n in range(1, 41):
            points = [[rng.randrange(-9, 10), rng.randrange(-9, 10)]
                      for _ in range(n)]
            for k in {0, 1, n // 2, n}:
                self.check_all(points, k)


if __name__ == "__main__":
    unittest.main()

รันผ่านจริงทั้งเทสต์ตัวอย่างและข้อมูลสุ่ม ครอบคลุมพิกัดลบ จุดซ้ำ ระยะเท่ากัน ขอครบทุกจุด และขอศูนย์จุด

Benchmark ที่รันจริง (20 ต.ค. 2026 บนเครื่องนี้)

เครื่องนี้ใช้ Python 3.14.7 จาก python3 -V และสถาปัตยกรรม x86_64 จาก platform.machine() วัดด้วย timeit โดยใช้ repeat=5, number=3 แล้วนำเวลาที่ดีที่สุดใน 5 รอบหาร 3 ให้เป็นเวลาต่อการเรียกหนึ่งครั้ง

ข้อมูลสร้างล่วงหน้าด้วย random.Random(20261020) สุ่มแต่ละพิกัดด้วย randrange(-10000, 10001) แยกเริ่ม seed ใหม่สำหรับแต่ละขนาด ทุกวิธีในแต่ละแถวได้ลิสต์เดียวกัน ไม่รวมเวลาสร้างข้อมูลและเทสต์ แต่รวมการคัดลอกลิสต์ การสร้างตัวสุ่มของลิง และการสร้างผลลัพธ์ตามโค้ดจริง ตารางเป็นมิลลิวินาที ปัดทศนิยม 3 ตำแหน่ง และตัวหนาคือเร็วสุดของแถวนั้น

n	k	หมี sorted	เพนกวิน heap	จิ้งจอก nsmallest	ลิง quickselect
10,000	10	1.756	1.064	0.487	1.948
10,000	5,000	1.593	2.924	2.997	3.756
200,000	10	51.332	20.917	9.252	36.787
200,000	100,000	47.773	139.238	162.444	42.980

เมื่อ k = 10 จิ้งจอกชนะทั้งสองขนาด เพราะเก็บผู้เข้ารอบน้อยและคำนวณคะแนนเพียงครั้งต่อจุด ส่วนเพนกวินสร้าง tuple ให้ทุกจุดจึงมีต้นทุนเพิ่ม เมื่อเลือกครึ่งหนึ่ง หมีชนะที่ 10,000 จุดเพราะงานเรียงหลักทำในโค้ด C ของ Python แต่ที่ 200,000 จุด ลิงชนะด้วยการลดงานเหลือเฉพาะกองที่เกี่ยวข้อง แม้ลูปแบ่งกองเขียนใน Python ทั้งสองแบบ heap แพงขึ้นเมื่อถังโตและต้องแทนสมาชิกมาก โดยจิ้งจอกยังต้องเรียงผู้เข้ารอบตอนท้ายด้วย ตัวเลขนี้ใช้กับเครื่องนี้ อินพุตนี้ และโค้ดนี้เท่านั้น ไม่รับประกันอันดับทุกชุดข้อมูลครับ

ตารางเลือกวิธีตามสถานการณ์

สถานการณ์	เลือก	เหตุผล
สัมภาษณ์ไวท์บอร์ด	เริ่ม sorted แล้วเสนอ heap	วางคำตอบที่ตรวจง่ายก่อน อธิบายการลดงานเมื่อ k เล็ก แล้วคุย quickselect ถ้าต้องการเวลาเฉลี่ยเชิงเส้น
โค้ดงานจริงที่เป็น hot path (production)	nsmallest เมื่อ k เล็ก แล้ววัดซ้ำกับข้อมูลจริง	ผลวัดนี้ชนะที่ k = 10 แต่เมื่อเลือกครึ่งหนึ่งต้องลอง sorted กับ quickselect
สอนมือใหม่	หมี sorted	เห็นความสัมพันธ์ระหว่างคะแนนกับลำดับ และใช้ตรวจวิธีซับซ้อนได้
ข้อมูลไหลมาเรื่อยๆ (stream)	เพนกวิน heap ขนาด k	อัปเดตคำตอบทุกครั้งที่มีจุดเข้า เก็บสถานะเพียง k จุด
k เล็กมากเทียบกับ n	จิ้งจอก nsmallest	เขียนสั้น ใช้พื้นที่ O(k) และชนะในสองแถวที่ k เล็ก
ต้องการผลลัพธ์เรียงลำดับด้วย	nsmallest ถ้า k เล็ก; sorted ถ้าเลือกมาก	ได้ลำดับมาเลย; heap และ quickselect ต้องเพิ่มขั้นตอนเรียงผล O(k log k)

ค่าเริ่มต้นภายใต้กติกาของโจทย์: ผมเริ่มด้วย heapq.nsmallest เมื่อยังไม่มีเงื่อนไขเพิ่ม เพราะอ่านง่ายและเหมาะกับการขอจุดใกล้จำนวนไม่มาก แล้วปรับตามสัดส่วน k/n และผลวัดจริง ไม่ถือว่าเร็วสุดทุกกรณี

บารอนสรุป

บารอน กระชับโค้ตแล้วเคาะค้อน: “รอบขอสิบจุด ข้ายกถ้วยให้จิ้งจอก ทั้งสองขนาดชนะชัดตามตาราง” “แต่รอบขอครึ่งกอง หมีชนะกองเล็ก ส่วนลิงชนะกองใหญ่ จึงไม่มีแชมป์ที่ใช้ได้ทุกสัดส่วน” เขาหันไปตบถังเพนกวินเบา ๆ “ถ้าข้อมูลเข้าทีละจุด เจ้าถังนี้ยังตอบโจทย์เรื่องสถานะและพื้นที่ได้ดี แม้ไม่ชนะเวลาในสนามนี้” ก่อนปิดศาลเขาย้ำว่าโจทย์รับคำตอบไม่เรียง จึงใช้ข้อได้เปรียบของ quickselect ได้ แต่ต้องยอมรับเวลาแย่สุดและค่าใช้จ่ายของการคัดลอกในเวอร์ชันนี้ด้วยครับ

Recap

เขียนคะแนน x*x + y*y แล้วลองกับพิกัดติดลบโดยไม่ถอดราก
ใช้ sorted สร้างคำตอบอ้างอิงก่อนลงมือเขียนวิธีอื่น
วาดถังขนาด k แล้วไล่ว่าจุดใดต้องออกเมื่อมีจุดใหม่เข้ามา
แบ่ง quickselect เป็นน้อยกว่า เท่ากัน มากกว่า แล้วลองข้อมูลระยะเท่ากันทั้งหมด
รัน unittest และตรวจคำตอบแบบรักษาจำนวนจุดซ้ำ พร้อมยอมรับลำดับอิสระ
วัดทั้ง k เล็กและ k ใกล้ครึ่งหนึ่งด้วยข้อมูลของงาน ก่อนเลือกวิธีใน hot path