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

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

对于最接近原点的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]

当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]

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


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

当元素频率范围已知时，采用桶排序可达到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]

结合快速排序的分区思想，通过随机化选择枢轴将时间复杂度优化至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))

针对重复元素的处理优化，采用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

在处理动态数据时，树状数组（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

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


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

问题类型	推荐算法	时间复杂度	适用场景
静态最近点	快速选择	O(n)	单次查询
动态数据流	堆结构	O(n logk)	实时更新
带重复元素	三向切分	O(n)	高重复数据集
位置查询	树状数组+二分	O(logn)	动态插入场景