c++ - 使用递归查找数组中第k个最小的元素？

#include <iostream>

using namespace std;

void moveToKthSmallest(int a[], int size, int k);


int main() {

int theArray[17] = {42, 5, 412, 56, 14, 98, 488, 4882, 24, 4, 9, 67, 9424, 2, 1, 3, 5};
int num;

cout << "Move to the kth smallest number in the array (size of 17): " << endl;
cin >> num;
moveToKthSmallest(theArray, 17, num);


return 0;
}

void moveToKthSmallest(int a[], int size, int k) {
int pivot = size / 2;
int pivotValue = a[pivot];
int index1 = 0, index2 = 0;
int s1[size], s2[size]; //not sure about this


for (int i = 0; i < size; i++) {
    if (a[i] < pivotValue) {
        s1[index1] = a[i];
        index1++;
    }
    else {
        s2[index2] = a[i];
        index2++;
    }
}

int s1Size = index1; //problem?
int s2Size = index2; //problem?

if (s1Size == k - 1) {
    cout << pivotValue;
}

else if (s1Size > (k - 1)) {
    moveToKthSmallest(s1, s1Size, k);
}

else if (s1Size < (k - 1)) {
    moveToKthSmallest(s2, s2Size, k - (s1Size - 1));
}
}

我要求用户输入一个数字（大于等于0或小于等于17），并且程序应在已生成的数组中输出第k个最小的数字。

以上是我的尝试，但是每次运行都会崩溃。我认为这与函数中数组s1和s2的声明以及从index1和index2生成的大小值有关。我尝试使用向量和动态数组，但是在编译器中不断收到错误消息，例如“错误：无法将参数'1'的'std :: vector **'转换为'int *'到'void moveToKthSmallest'..老实说，我不太确定那是什么意思。

我在这里错过明显的东西吗？

最佳答案

第一步是将其标记为C ++而不是C。因此，应该使用简单的int a[]代替int size和std::vector<int>。

现在，在您的示例中，每次进行递归操作时，您都要遍历整个数组。

第二点，我不明白为什么这里甚至需要递归。只需在数组上进行一次迭代即可找到答案。

最简单的方法是使用第二个数组，例如std::vector<int> smallest，然后仅对std::vector<int> a进行一次迭代。

遍历每个元素时：


如果smallest.size()已经是k，并且当前值大于smallest中的最后一个值，则继续执行a中的下一个值，否则删除smallest中的最后一个值。
此时，smallest.size()始终小于k，因此，将a中的当前值添加到smallest中，以使smallest数组保持排序顺序。


在迭代结束时，smallest向量中的最后一个值是原始向量中的第k个最小值。

如果您想知道第k个最小值的位置，则可以通过跟踪smallest向量中的位置而不是该值来对上述算法进行较小的修改。

这似乎是一个更简单，直接的解决方案，然后是一个复杂的基于递归的方法，并且具有令人困惑的枢轴操作。同样，您的透视示例要求修改原始数组，而我的方法则不需要，并且甚至可以与const std::vector<int>一起使用。

附言确实没有必要将smallest保持在已排序的顺序中。稍加修改算法，smallest就可以保持未排序状态。此处的作业分配是调整此算法，以使其不要求smallest保持排序顺序。