SELECTION IN X + Y，二维数组的Top K问题

2020-08-23 本文已影响0人 devilisdevil

algorithm: SELECTION IN X + Y AND MATRICES WITH SORTED ROWS AND COLUMNS *
leetcode: 378. Kth Smallest Element in a Sorted Matrix

问题描述

$n \times n$ 的二维数组，行列均有序，寻找第k大元素

为了方便对算法理解，这里假设行列的数都是递增的，比如像下面这样：

Example Matrix

算法分析

思想：分治 divide-and-conquer

一些定义：

符号	说明
$A$	$n \times n$ 的矩阵/二维数组
$\overline{n}$	$\left \lceil \frac{1}{2} (n+1) \right \rceil$
$\overline{A}$	$A$ 的 $\overline{n} \times \overline{n}$ 大小的子矩阵，取 $A$ 的奇数行列得到（外加最后一行/列，如果 $n$ 是偶数），
$rank^+(A, a)$ / $rank^-(A, a)$	集合(矩阵) $A$ 中大于/小于 $a$ 的元素个数

例如， $6 \times 6$ 的矩阵 $A$ 对应的子矩阵 $\overline{A}$ 由黄色块组成

the submatrix of A

算法主要需要实现两个函数： $biselect$ 和 $pick$

pick

函数功能：求第k小元素 (the k-th element of L)

一般quickselect的最坏复杂度是 $O(nlogn)$ ，但若运用上median of medians（BFPRT算法，选取中位数附近的数作为partition的点），最坏复杂度可降为 $O(n)$ ，所以该paper也是使用的这个 $O(n)$ 的算法。
关于该算法的讲解，参考我另一篇文章：中位数的中位数 - Median of Medians，选取近似的中位数作为pivot元素，这里不再赘述，最后总的实现可以看我github上的代码。

biselect

函数功能：选取方阵中的两个元素，第 $k_1$ 小和第 $k_2$ 小元素。而如果我们需要寻找第 $k$ 小的元素，直接传参 $k_1=k_2=k$ 就行了

biselect pseudo code

上面是paper中的伪代码，这里对 $ra^-$ ， $rb^+$ 和 $L$ 的计算可以同时进行，如下：（这里的矩阵是右下角对应最大，左上角最小，如果矩阵的行列排序不同的话你可能需要调整一些加减符号，但计算的思想可以借鉴）

int ra_less = 0, rb_more = 0;
vector<int> L;
int ja = n, jb = n;
for (int i = 0; i < n; ++i) {
  while (ja > 0 && A(i, ja - 1) >= a) --ja;
  ra_less += ja;
  while (jb > 0 && A(i, jb - 1) > b) --jb;
  rb_more += n - jb;
  //                  jb   ja
  // each row: ---bbb[x]xx[a]aa+++
  // append x's to L (b < x < a)
  for (int ii = jb; ii < ja; ++ii) L.push_back(A(i, ii));
}

最后最重要的是分治算法的combine部分：计算x和y的值并返回

line of elements.png

如上图，要明白伪代码最后几行判断条件，只要理解上面这个图就ok了。

首先，这条线上代表A中的元素的从小到大排列，一共 $n \times n$ 个元素
$\overline{A}$ 中第 $\overline{k}_1$ 小元素为 $a$ ，第 $\overline{k}_2$ 小元素为 $b$ ， $\overline{k}_2 <= k_2 <= k_1 <= \overline{k}_1$ 。
k1_ k2_.png

现在自己再去理解上面的几个判断条件吧。。
关键在于为什么 $\overline{k}_1$ 和 $\overline{k}_2$ 这么赋值，请看下面的正确性说明。

SELECTION IN X + Y，二维数组的Top K问题

问题描述

算法分析

pick

biselect

正确性

示例代码

参考

猜你喜欢

热点阅读