將相似類型的元素放在一起

Question

我在某處閱讀了這個採訪問題並試圖解決它：

給定一個水果攤（最多8種不同類型的水果）。將相似類型的水果放在一起。 限制：a）水果攤位是你的整個世界（即不使用額外的空間），b）取得一個水果並知道它的類型（getType（））是一個代價高昂的操作，但交換是一個非常便宜的操作。

注意：您需要編寫代碼來處理牢記所有情況下的最大種類的水果可8.

所以，它會彈出在我的腦海中，我們需要調用的getType想法（）對於所有的水果（數組元素），然後根據特定的類型對它們進行相應的排序。如果不知道水果的種類以及可以解決這個問題的最佳解決方案，我無法在這裏完成交換。

Answer 1

既然這是一個面試問題，我會假設你的水果攤是一個數組。將數組分成八個區域，以便每個區域只包含給定類型的果實，使用七個指針，其中一個指向除第一個區域之外的每個區域的起點。使用第八個指針指向未分類區域的開始位置。

初始化指向數組開頭的指針。獲得指針的定義是棘手的，因爲你必須覆蓋沒有給定類型的結果的情況。一個可能的定義是，指針i包含到目前爲止對類型（包括i）進行排序的水果數量，對於i = 1..8。然後在開始時所有的指針被設置爲等於零並且1 1 1 2 2 3 4 4 |對應於p1 = 3 p2 = 5 p3 = 6 p4 = 8 p5 = p6 = p7 = p8 = 8

重複查看未分類區域開始處的第一個果實以查明其類型。如果不應該進入最後區域，則將其與最終區域開始處的元素進行交換，並將指針推進到最終區域的開始位置。如果它不應該進入第二個區域，則將其與第二個最後區域的開始處的元素進行交換，並將指針前進到第二個最後區域的開始處......等等，直到新水果處於其正確位置。現在將指針移至第一個未排序的水果並重復。

這看每個水果一次，我不認爲你可以用更少的調用排序getType（）。你不關心掉期的數量，所以我認爲這是最佳的。

我會放入顯示以c1，c2，c1，c3，c2，c1，c4，c4開頭的交換。我不會在cs中寫字，我會使用|劃分左邊的區域，其中所有的東西都是從右邊的區域開始依次類型是未知的

| 1 2 1 3 2 1 4 4

1 | 2 1 3 2 1 4 4

1 2 | 1 3 2 1 4 4

1 1 | 2 3 2 1 4 4

1 1 2 | 3 2 1 4 4

1 1 2 3 | 2 1 4 4

1 1 2 2 | 3 1 4 4

1 1 2 2 3 | 1 4 4

1 1 2 2 1 | 3 4 4

1 1 1 2 2 | 3 4 4

1 1 1 2 2 3 | 4 4

1 1 1 2 2 3 4 | 4

1 1 1 2 2 3 4 4 |

Answer 2

這很可能是作爲就地合併排序完成的。正如你所提到的，立即檢查每種水果的種類。這不會佔用任何額外的內存（有關如何進行就地合併排序的許多指南）只會調用一次getType（），並且將導致nlog(n)運行時間和n內存使用量。

有沒有我們知道的任何信息？似乎這個問題的措辭是這樣的，他們通常會給我們一種替代方式來避免必須進行n次呼叫。如果這是一個面對面的問題，如果這個練習的目標應該隨着面試官開始進入而發展，那麼不要感到驚訝。這可以解釋爲什麼他們特別提到getType()是昂貴的