如何用代码解决最近点问题？最接近原点的 K 个点和前 K 高频元素你搞懂了吗？

在推荐系统优化、大数据分析等场景中，我们常面临两个经典问题：如何从数百万坐标点中快速找出距离原点最近的K个点？如何在海量数据流中精确统计出现频率最高的K个元素？这两个问题看似简单，但在时间复杂度和空间复杂度双重约束下，需要开发者深入理解分治策略、堆结构、快速选择等核心算法，并掌握树状数组等高级数据结构的组合应用。

一、分治策略：二维空间最近点问题

1.1 平面坐标的快速筛选

对于最接近原点的K个点问题，常规解法是对所有点进行全量距离计算并排序。但在坐标点数量超过10^6时，O(n logn)的时间复杂度将产生性能瓶颈。此时可采用分治策略：

def k_closest(points, k):
    points.sort(key=lambda x: x[0]2 + x[1]2)
    return points[:k]

1.2 时间复杂度优化

当K值远小于n时，使用最大堆（Max Heap）可将时间复杂度优化至O(n logk)。通过维护容量为K的堆结构，每次仅需比较堆顶元素：

import heapq

def k_closest_heap(points, k):
    heap = []
    for (x, y) in points:
        dist = -(xx + yy)
        if len(heap) < k:
            heapq.heappush(heap, (dist, x, y))
        else:
            heapq.heappushpop(heap, (dist, x, y))
    return [(x,y) for (dist,x,y) in heap]

二、堆结构：前K高频元素统计

2.1 频率统计与堆应用

统计元素频率时，哈希表与最小堆的组合可有效降低时间复杂度。通过字典统计频率后，使用堆维护Top K元素：

def top_k_frequent(nums, k):
    count = collections.Counter(nums)
    return heapq.nsmallest(k, count.keys(), key=lambda x: -count[x])

2.2 桶排序优化法

当元素频率范围已知时，采用桶排序可达到O(n)时间复杂度。为每个频率建立存储桶，逆向遍历获取前K高频元素：

def top_k_bucket(nums, k):
    count = collections.Counter(nums)
    buckets = [[] for _ in range(len(nums)+1)]
    for num, freq in count.items():
        buckets[freq].append(num)
    
    res = []
    for i in range(len(buckets)到1, 0, 到1):
        res.extend(buckets[i])
        if len(res) >= k:
            break
    return res[:k]

三、快速选择算法：双K问题的通用解法

3.1 快速选择原理

结合快速排序的分区思想，通过随机化选择枢轴将时间复杂度优化至O(n)。该算法尤其适合处理重复元素较多的情况：

import random

def quick_select(nums, k):
    pivot = random.choice(nums)
    lows = [x for x in nums if x < pivot]
    highs = [x for x in nums if x > pivot]
    pivots = [x for x in nums if x == pivot]
    
    if k < len(lows):
        return quick_select(lows, k)
    elif k < len(lows) + len(pivots):
        return pivots[0]
    else:
        return quick_select(highs, k len(lows) len(pivots))

3.2 三向切分优化

针对重复元素的处理优化，采用Dijkstra三向切分法减少元素比较次数：

def three_way_partition(arr, low, high):
    lt = low
    gt = high
    i = low
    pivot = arr[low]
    while i <= gt:
        if arr[i] < pivot:
            arr[i], arr[lt] = arr[lt], arr[i]
            lt += 1
            i += 1
        elif arr[i] > pivot:
            arr[i], arr[gt] = arr[gt], arr[i]
            gt -= 1
        else:
            i += 1
    return lt, gt

四、树状数组与二分法的组合应用

4.1 动态区间查询

在处理动态数据时，树状数组（Fenwick Tree）与二分查找的组合能高效解决序列位置查询问题。其核心思想是通过维护前缀和实现快速区间统计：

class FenwickTree:
    def __init__(self, size):
        self.n = size
        self.tree = [0](self.n+1)
    
    def update(self, idx, delta):
        while idx <= self.n:
            self.tree[idx] += delta
            idx += idx & -idx
    
    def query(self, idx):
        res = 0
        while idx > 0:
            res += self.tree[idx]
            idx -= idx & -idx
        return res

4.2 二分定位算法

结合树状数组的前缀和查询，通过二分法快速定位目标位置：

def find_kth_empty(bit, k, n):
    low = 1
    high = n
    while low < high:
        mid = (low + high) // 2
        count = mid bit.query(mid)
        if count >= k + 1:
            high = mid
        else:
            low = mid + 1
    return high

五、算法选择指南

关键选择原则：
1. 数据规模小于10^5时优先选择快速选择算法
2. 需要实时维护Top K时采用堆结构
3. 存在动态插入删除操作时结合树状数组
4. 内存敏感场景优先考虑原地操作算法

通过深入理解这些算法的核心原理与实现细节，开发者能够根据具体业务场景选择最优解决方案。算法优化的本质是在时间复杂度、空间复杂度和代码可维护性之间找到最佳平衡点。