使用遞歸在數組中尋找第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個最小數字。使用遞歸在數組中尋找第k個最小的元素？

以上是我的嘗試，但每次運行它都會崩潰。我認爲這與函數中的數組s1和s2的聲明以及從index1和index2生成的大小值有關。我試過使用向量和動態數組，但我一直在我的編譯器中收到錯誤消息，例如「錯誤：不能將'std :: vector **'轉換爲'int *'作爲參數'1'到'void moveToKthSmallest」。說實話，我不太清楚這意味着什麼。

我在這裏錯過了一些明顯的東西嗎？

來源

2015-10-17 dc90

-1

第一個問題是，它被標記爲C++而不是C。因此，您應該使用一個簡單的std::vector<int>而不是int a[]和int size。

現在，在這個例子中，在你的例子中，每當你遞歸的時候你就遍歷整個數組。

第二個問題，我不明白爲什麼在這裏甚至需要遞歸。答案可以在您的數組上單次迭代找到。

這樣做最簡單的方法是使用第二個數組，比如說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>一起使用。

P.S.按照排序順序保存smallest並不是必須的。通過稍微修改算法，smallest可以保持未排序。此處的作業分配是調整此算法，以便不要求smallest保持排序順序。

來源

2015-10-17 21:38:47

使用遞歸在數組中尋找第k個最小的元素？

回答

相關問題