Kth Small Number with Divide-and-Conquer

Selection问题

题目描述

有一道经典的算法题”Selection”

SELECTION
Input: A list of numbers S; an integer k
Output: The kth smallest element of S
For instance, if k = 1, the minimum of S is sought, whereas if k = |S|/2, it is the median.

算法分析

这道题有很多解法，最简单的就是先对所有数排序。但是显然当数据较大时，这种方法效率不高。使用分治算法就可以在此基础上提高效率，因为只需对一部分而不是全部数据进行排序。
大致思路如下：每一次，先从数组中选出任意一个参考数pivot。选取的方法几乎不会影响效率，一般来说随机选取即可。选取好pivot后，对数组进行遍历，将所有数据分为三组，即小于，等于，大于pivot的三组。例如：

若选取5作为参考数，则分成的三组为：

分组后，根据各组中数的数量，即可进行下一层递归，因此算法如下：

代码实现

综上所述，可以得到其代码实现：

int findNumberK(vector<int> &vec, int k) {
    vector<int> s_vec, e_vec, l_vec;
    int pivot = vec[vec.size() / 2];        // 选取参考值
    for (int i = 0; i < vec.size(); i++) {  // 遍历并分组
        if (vec[i] < pivot) {
            s_vec.push_back(vec[i]);
        }
        else if (vec[i] == pivot) {
            e_vec.push_back(vec[i]);
        }
        else {
            l_vec.push_back(vec[i]);
        }
    }
    if (k <= s_vec.size()) {                // 进入下一层递归
        return findNumberK(s_vec, k);
    }
    else if (k > s_vec.size() + e_vec.size()) {
        return findNumberK(l_vec, k - s_vec.size() - e_vec.size());
    }
    else {
        return pivot;
    }
}

这就是Selection问题的分治解法。

分治算法寻找第K小数

问题描述

LeetCode上有这么一道类似Selectiond的变种题目：

378. Kth Smallest Element in a Sorted Matrix
Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.
Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example:

matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,
return 13.

Note:
You may assume k is always valid, 1 ≤ k ≤ n2.

算法分析

这道题对比与Selection问题，所有在matrix中的数，更为“有序”，因为在其任何一列或任何一行上的数，都是有序的。因此在这里利用的是上题的思路，而由于这些数据在矩阵中是相对有序的，使用了二分查找的方法，就能较为高效地得到答案。这次采用的是非递归的方法。
基本思路是：每次遍历矩阵，得到小于或等于参考数median的数量，以此决定下一次筛选的范围。

代码实现

class Solution {
public:
    int findKthNumber(int m, int n, int k) {
    int small = 1, large = m * n;
    while (small < large) {
        int median = (small + large) / 2;
        int count = 0;
        // 遍历找出所有小于或等于median的数并计数
        for (int row = 1; row <= m; row++) {
            if (row * n <= median) {
                count += n;
            } else {
                count += median / row;
            }
        }
        // 根据计数结果，进行下一步筛选
        if (count < k) {
            small = median + 1;
        }
        else {
            large = median;
        }
    }
    return small;
    }
};

本文为博主原创文章，转载请注明出处。