分類
Swift

一道 華為 面試 的 編程算法 題

今天朋友發來一道很特別的題目:

題目:有兩個數組a,b,大小都為n,數組元素的值任意,無序;
要求:通過交換a,b中的元素,使數組a元素的和與數組b元素的和之間的差最小。

我乍一看這個題感覺眼熟……和國內各種C語言考試基本上差不多,不過仔細一看似乎還有點難度,不像那種一看就有頭緒的問題。好吧,一問才知道,這是華為的一道面試題目。

畢竟是面試,所以還是稍微有點難度的。——但畢竟是國內啊……這個題目也真是向老譚致了足夠多的敬了。考慮到它主要考的是算法,那麼就和語言無關了,我就用我最熟悉的 Swift 來完成它。

其實這道題有誤導啊,它故意強調了“無序”和“交換”讓你去想如何計算——其實,只要打亂重排就好了——注意數組的長度要固定——我想這就是為什麼數組的大小都為相同的n。另外說的那麼複雜,其實目的就是說兩個數組裡的數字加起來要盡可能的接近罷了,所以,我就先寫了個遍歷數組求和的函數備用:

這個函數接收一個數組來遍歷求和,然後把結果返回。

然後呢,我設定了兩個長度相同的數組:

這裡我們都默認數字類型是整形,因為好計算,其實算法也可以應用與小數,這一點題中沒有給出明確的說明,但考慮到可能要用C語言實現,我們還是不要擼泛型了先。

首先,我們寫一個函數用來處理這兩個數組,最終返回一個帶有兩個數組的元組。這個元組裡就包含了兩個經過互換元素的數組,他們的和應當盡可能地接近——即差要盡可能等於零。

然後,不是對比和交換——這不是排序——好吧,其實某種意義上來說這還是排序,我們只需要把數組打散放入池中,然後依次從大到小取出分別放入兩個數組就好了。

數組依次分配
數組依次分配

可是隨後我就發現了這個方法的一個bug!那就是如果我的數組不是平均的呢?比如其中某個數組裡有個極大值,那結果就不這麼理想了:

如果有極大數或者極小數的時候
如果有極大數或者極小數的時候

而我們期望的結果則是有極大數的一邊都是較小的數補齊,而另一邊則是剩下盡可能大的數字來填充,這樣兩者之間的差才最小:

這才是我們期望的結果
這才是我們期望的結果

那麼怎麼來判斷呢?我們只需要判斷數組(元素之和)哪個大哪個小不就行了?我們之前不就恰好寫了一個求數組元素之和的函數嗎,這不就派上了用場:)

那麼現在我們只需要實現把傳入的數組打碎再重組排序放入那個 Pool 裡邊就好了!

這裡我用了一個結構體來做了一個堆棧,把排序好的數組扔進去,這樣會很直觀——其實你可以直接用數組,只不過那樣看起來不太好看就是了。

那麼,配合堆棧,我們的函數就應該是這樣:

等等,這樣好像哪裡不對……運行的結果是這樣的:

哈哈,看來我們需要一個變量來追踪一下數組的長度,不然分分鐘跑題啊!

所以說,如果數組的長度不同,那麼我們的函數也不應該執行,那麼我們增加一個判斷,如果參數不正確(也就是說,輸入的兩個數組長度不同),函數就不執行,避免數組越界。

那麼,們的函數最終的結果是這樣的:

這樣,我們就得到了最終的代碼:

代碼執行的結果是:

 

本文由 落格博客 原創撰寫:落格博客 » 一道 華為 面試 的 編程算法 題

轉載請保留出處和原文鏈接:https://www.logcg.com/archives/1461.html

通過 落格博客

如非聲明,本人所著文章均為原創手打,轉載請註明本頁面鏈接和我的名字。

發表評論

您的電子郵件地址不會被公開. 必填字段標 *