假設您有一個方法subArrayLeftShift(a,i)，當 n 是數組長度時，該方法將子數組 a[i,...,n-1] 左移。這意味著元素 a[i+1],...,a[n-1] 向左移動了一個位置，而原來的 a[i] 將成為最后一個。更正式地，這里是函數實現：public static void subArrayLeftShift(int[] a, int i){ if (a.length == 0) return; int last = a.length - 1; int insertToLast = a[i]; for (; i < last; i++){ a[i] = a[i + 1]; } a[last] = insertToLast;}現在的問題是：實現一個接收未排序數組的函數，并返回對數組排序的最少調用次數subArrayLeftShift。在采訪中，我找不到辦法做到這一點。我成功地為我為直覺而編寫的每個示例找到了最少的調用次數，但找不到概括它的方法。你知道如何解決嗎？
2 回答
猛跑小豬
TA貢獻1858條經驗 獲得超8個贊
我提出以下算法來解決這個問題：
找出數組中未排序的最小數字（數組右側的數字較小）。將此數字設為x。
計算數組中有多少數字大于先前找到的數字x。將此數字設為y。
由于每次調用函數時，未排序的數字都會在最后一個位置結束，因此最佳策略是按遞增順序為每個未排序的數字調用函數。使用之前找到的內容，我們從x開始。我們繼續(xù)下一個大于 x 的未排序數字，因為這樣，它將在x的右側結束，因此它將被排序。以同樣的方式繼續(xù)。多少？我們有多少比x大的數？嗯，就是y。所以總的來說，對該函數的調用次數是1 + y。
ABOUTYOU
TA貢獻1812條經驗 獲得超5個贊
public static int minimumCalls(int[] a) {
int minCalls = 0;
for (int i = 0; i < a.length - 1; i++) {
for (int j = i+1; j < a.length; j++) {
if (a[i] > a[j]) {
minCalls++;
break;
}
}
}
return minCalls;
}
我的想法背后的想法是，只要 SubArray 中存在任何小于 current 的值，就必須調用該方法一次i。subArrayShiftLeft我覺得這個方法的名字是為了讓你遠離并把你的注意力從容易地想這個問題上拉開。
如果數組中有任何小于當前值的值，只需調用該方法。
將此視為將單個較大的值移動到數組的末尾比嘗試將較小的值向左移動要容易得多。
添加回答
舉報
0/150
提交
取消