找出第k小的元素内存超限怎么解决

Question

应该算是竞赛题要求，一直显示内存超限，不知道为什么，救命救命

对于给定的n个元素的数组a[0:n-1]，从中找出第k小的元素并输出。
测试数据有多组，每组占两行，第一行是整数n和k（1≤k<n≤1000），第二行是n个整数，各整数之间均由一个空格分隔。
输出第k小的元素。

输入:
5 2
3 9 4 1 6
7 3
4 59 7 23 61 55 46
输出:
3
23

代码

#include<iostream>

using namespace std;

int select(int a[],int k,int left,int right){
    int l, r,key;
    l = left;
    r = right;
    key = a[left];
    while (l < r&&a[r] >= key)r--;
    if (l < r){ a[l] = a[r]; l++; }
    while (l < r&&a[l] <= key)l--;
    if (l < r){ a[r] == a[l]; r++; }
    a[l] = key;
    if (l == k - 1)
        return a[l];
    else if (l>k - 1)select(a, k, left, l - 1);
    else select(a, k, l + 1, right);
 
}
 
int main(){
    int n, k, *a;
     
    while (cin >> n){
        a = new int[n];
        cin >> k;
        for (int i = 0; i < n; i++)
            cin >> a[i];
        cout << select(a,k,0,n-1) << endl;
        delete[] a;
    }
}

Answer 1

【以下回答由 GPT 生成】

问题分析： 代码中使用的递归方式实现了一个选择算法来找到第k小的元素。然而，使用递归在处理大量数据时可能会导致内存超限的问题。我们可以通过改变算法或优化代码来解决这个问题。

解决方案： 1. 利用迭代代替递归：递归可能会导致栈溢出，因为它会在每一次递归调用时都保存一些数据。我们可以使用循环来代替递归，减少内存使用。下面是修改后的代码：

int select(int a[], int k, int left, int right){
    while (true){
        int l, r, key;
        l = left;
        r = right;
        key = a[left];
        while (l < r && a[r] >= key)
            r--;
        if (l < r){ 
            a[l] = a[r]; 
            l++;
        }
        while (l < r && a[l] <= key)
            l++;
        if (l < r){ 
            a[r] = a[l]; 
            r--;
        }
        a[l] = key;
        if (l == k - 1)
            return a[l];
        else if (l > k - 1)
            right = l - 1;
        else
            left = l + 1;
    }
}

1. 使用堆排序：堆排序可以在不占用额外内存的情况下找到第k小的元素。我们可以使用C++的priority_queue类来实现堆排序。下面是修改后的代码：

#include<iostream>
#include<queue>
#include<vector>

using namespace std;

int main(){
    int n, k;
    while (cin >> n){
        vector<int> a(n);
        cin >> k;
        for (int i = 0; i < n; i++)
            cin >> a[i];
        priority_queue<int, vector<int>, greater<int>> pq(a.begin(), a.end());
        for (int i = 1; i < k; i++)
            pq.pop();
        cout << pq.top() << endl;
    }
    return 0;
}

以上是两种解决内存超限问题的方法，你可以根据具体场景选择其中一种来解决你的问题。

【相关推荐】

• 这有个类似的问题, 你可以参考下: https://ask.csdn.net/questions/7610262

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^