c++ - 在未排序的非负整数数组中找到第 k 个最小的元素

Question

不允许修改数组(数组是只读的)。允许使用常量额外空间。

例如:答:[2 1 4 3 2]k : 3

答案:2

我是按照下面的方法做的。答案是正确的，但需要提高内存效率。

void insert_sorted(vector<int> &B, int a,int k)
{
    for(int i=0;i<k;i++)
    {
        if(B[i]>=a)
        {
            for(int j=k-1;j>i;j--)
                B[j]=B[j-1];
            B[i]=a;
            return;
        }
    }
}

int Solution::kthsmallest(const vector<int> &A, int k) {

    vector <int> B;
    for(int i=0;i<k;i++)
    {
        B.push_back(INT_MAX);
    }
    int l=A.size();

    for(int i=0;i<l;i++)
    {
        if(B[k-1]>=A[i])
            insert_sorted(B,A[i],k);
    }

    return B[k-1];
}

Answer 1

一种可能的解决方案是二分查找。

设A为输入数组；我们想找到一个数 b 使得 A 中恰好有 k 项小于 b。

显然，b 必须在 [0, max(A)] 范围内。我们从这个范围开始进行二进制搜索。

假设我们在 [lo, hi] 范围内搜索。设 c = (lo + hi)/2 是中间枢轴。分三种情况:

• A 中小于c 的项数小于k。在这种情况下，我们搜索的数字应该大于 c，因此它应该在 (c, hi]

范围内

• A 中小于c 的项数大于k。同样，我们搜索的数字在[lo, c)

范围内

• A 中小于c 的项数等于k。在这种情况下，答案是 A 中大于或等于 c 的最小元素。这可以通过再次在 A 中进行线性搜索来找到

复杂度为O(n log m)，其中m是A中的最大元素。

/* assume k is 0 based, i.e. 0 <= k < n */
int kth_element(const vector<int> &A, int k){
    int lo = 0, hi = *max_element(A.begin(), A.end());
    while (lo <= hi){
        int mid = (lo + hi) / 2;
        int rank_lo = count_if(A.begin(), A.end(), [=](int i){ return i < mid;}); 
        int rank_hi = count_if(A.begin(), A.end(), [=](int i){ return i <= mid;});

        if (rank_lo <= k && k < rank_hi)
            return mid;

        if (k >= rank_hi)
            lo = mid + 1;
        else
            hi = mid - 1;
    }
}

---

虽然这不是这个特定问题的答案(因为它需要一个可修改的集合)，但有一个名为 std::nth_element 的函数，它重新排列元素以便 k第k元素，所有k位置的元素都小于等于第k元素，其中 k 是输入参数。