前往
大廳
主題

LeetCode - 1968. Array With Elements Not Equal to Average of Neighbors 解題心得

Not In My Back Yard | 2022-01-20 00:00:04 | 巴幣 0 | 人氣 118

題目連結:


題目意譯:
你被給定一個索引值從 0 開始的相異整數陣列 nums。你想要重新排列陣列中的元素使得重新排列後的陣列中的每個元素不等於其鄰居的平均值。

更正式地說,重新排列後的陣列應有著一性質,其滿足每個於範圍 1 ≦ i < nums.length - 1 的索引值 i,(nums[i - 1] + nums[i + 1]) ÷ 2 不等於 nums[i]。

回傳任意一種 nums 滿足上述要求之重新排列的方式。

限制:
3 ≦ nums.length ≦ 10 ^ 5
0 ≦ nums[i] ≦ 10 ^ 5



範例測資:
範例 1:
輸入: nums = [1,2,3,4,5]
輸出: [1,2,4,5,3]
解釋:
當 i = 1,nums[i] = 2,而其鄰居的平均為 (1 + 4) ÷ 2 = 2.5。
當 i = 2,nums[i] = 4,而其鄰居的平均為 (2 + 5) ÷ 2 = 3.5。
當 i = 3,nums[i] = 5,而其鄰居的平均為 (4 + 3) ÷ 2 = 3.5。

範例 2:
輸入: nums = [6,2,0,9,7]
輸出: [9,7,6,2,0]
解釋:
當 i = 1,nums[i] = 7,而其鄰居的平均為 (9 + 6) ÷ 2 = 7.5。
當 i = 2,nums[i] = 6,而其鄰居的平均為 (7 + 2) ÷ 2 = 4.5。
當 i = 3,nums[i] = 2,而其鄰居的平均為 (6 + 0) ÷ 2 = 3。


解題思維:
把陣列由小到大排序,然後把陣列分成數字較小以及數字較大兩個部分(如果數字個數為奇數,則最中間那個數字實際上分到哪邊都可以。但為了方便起見,請分到較小那一半)。

接著把較大的那一半反轉,然後一個數字一個數字安插在較小那一半每兩個相鄰數字之間。

例如 nums = [4, 8, 7, 6, 3],我們由小到大排序後分成 [3, 4, 6] 以及 [7, 8] 這兩半。將較大那一半反轉並安插到較小那一半後,將會得到 [3, 7, 4, 8, 6]。

可以看到這樣的排列即符合題目的要求。原因是,我們在較小的那一半兩兩數字之間安插一個較大的數字,因此兩個較小數字的「平均」絕對不可能等於較大的數字(因為題目有說所有數字相異)。



而實際上我們可以看到這個排列,即是兩天前的題目——扭動排序(Wiggle Sort),而該種排序可以在線性時間得到,參見這篇心得




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作