我需要在未排序的陣列中找到第 n 個最小值，當然不對其進行排序。該函式需要遞回。我想過下面的代碼，但這不起作用，因為我可能會錯過小陣列中的一些值。有什么建議 ？
例子：
array ={5,2,10,11,18,3,7,9,15,17}
index = 3
expected return = 7
index=7
expected return = 15
int func(int arr[], int size, int index)
{
//if we cant divide the array anymore
if (size == 1)
return arr[0];
//if we don't need to divide the array anymore
if (index == 1)
return findMinInArr(arr, size);
//split the array to 2 arrays and work on lower level
return Max(func(arr, size / 2, index / 2), func(arr size / 2, size - size / 2, index - index / 2));
}
uj5u.com熱心網友回復：
您的方法失敗了，因為在找到您感興趣的價值時，沒有理由將分割成兩半是有意義的。
例如，假設您需要第二個最小值。可能的情況是最小值和第二小值都在陣列的前半部分；而后半部分只有非常大的值。您的使用Max()將導致您的函式回傳這些值之一。
相反，請考慮：
如果這些值都是不同的，則實作一個函式來找到不小于給定值的最小值，并將其用作構建塊。
使用您可能已經了解的排序演算法之一對陣列進行部分排序。
這些是提示，因為我懷疑您在問我們一個“家庭作業問題”，您應該努力自己解決它。
uj5u.com熱心網友回復：
我相信你走錯了路，試圖劃分你的陣列。
我想用 替換陣列中的最小數字INT_MAX，所以想法是做類似（偽代碼）的事情：
int get_smallest(array, index)
{
if index==0
then return smallest(array);
else
{
replace_smallest_number_by_INT_MAX(array);
return get_smallest(array, index - 1);
}
}
所以，當你運行它時，你會有這樣的行為：
get_smallest({5 , 2 , 10, 11, 18, 3 , 7, 9, 15, 17}, 3)
= get_smallest({5 , INT_MAX, 10, 11, 18, 3 , 7, 9, 15, 17}, 2)
= get_smallest({5 , INT_MAX, 10, 11, 18, INT_MAX, 7, 9, 15, 17}, 1)
= get_smallest({INT_MAX, INT_MAX, 10, 11, 18, INT_MAX, 7, 9, 15, 17}, 0)
= 7
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/349066.html
上一篇：磚在墻上的排列方式共有多少種？