題目連結:
題目意譯:
給定一個整數陣列 nums,其中 nums[i] 只會是一個正整數或是 -1。我們需要為每一個 -1 找到對應的正整數。
為了達成這個目標,定義兩個空的陣列:seen 和 ans。
從陣列 nums 的開頭開始掃過各個元素:
如果碰到了一個正整數,將其放到 seen 的開頭;
如果碰到了一個 -1,令 k 為當前看到的連續 -1 數量(包含當前這個 -1),則
如果 k 小於等於 seen 的長度,將 seen 的第 k 個元素放到 ans 的結尾;
如果 k 大於 seen 的長度,將 -1 放到 ans 的結尾。
回傳陣列 ans。
限制:
1 ≦ nums.length ≦ 100
nums[i] == -1 or 1 ≦ nums[i] ≦ 100
範例測資:
範例 1:
輸入: nums = [1,2,-1,-1,-1]
輸出: [2,1,-1]
解釋:
一開始 seen = [] 且 ans = []。
碰到 nums[0]: nums 中第一個元素是 1。我們將其放到 seen 的開頭?,F在 seen == [1]。
碰到 nums[1]: 下一個元素是 2。我們將其放到 seen 的開頭?,F在 seen == [2, 1]。
碰到 nums[2]: 下一個元素是 -1。這個是第一個 -1,所以 k == 1。找到 seen 的第一個元素。將 2 放到 ans 結尾?,F在 ans == [2]。
碰到 nums[3]: 另一個 -1。這是連續第二個 -1,所以 k == 2。seen 中的第二個元素是 1,所以將 1 放到 ans 結尾。現在 ans == [2, 1]。
碰到 nums[4]: 另一個 -1,連續第三個,k == 3。不過此時因為 seen 只有兩個元素([2, 1]) 。因此將 -1 放到 ans 結尾。最終 ans == [2, 1, -1]。
範例 2:
輸入: nums = [1,-1,2,-1,-1]
輸出: [1,2,1]
解釋:
一開始 seen = [] 且 ans = []。
碰到 nums[0]: nums 中第一個元素是 1。我們將其放到 seen 的開頭。現在 seen == [1]。
碰到 nums[1]: 下一個元素是 -1。這個是第一個 -1,所以 k == 1。找到 seen 的第一個元素。將 1 放到 ans 結尾?,F在 ans == [1]。
碰到 nums[2]: 下一個元素是 2。我們將其放到 seen 的開頭?,F在 seen == [2, 1]。
碰到 nums[3]: 下一個元素是 -1。由於 2 夾在中間,所以這個 -1 跟第一個並不連續。因此 k == 1。seen 中的第一個元素是 2。將 2 放到 ans 結尾。現在 ans == [1, 2]。
碰到 nums[4]: 另一個 -1,。這個 -1 跟前一個是連續的,所以 k == 2。seen 中第二個元素是 1,將 1 放到 ans 結尾。最終 ans == [1, 2, 1]。
解題思維:
沒什麼特別的,按題目說的模擬即可。
不過如果有讀者嫌「每一次新的數字要加在 seen 的前面的這個過程會讓其他數字先『往後移一個位置』再放數字』的這件事情實在是很沒有效率的話,那可以改放在 seen 的結尾。不過這個時候要存取「第 k 個元素」時不再是 seen[k - 1] 了,而是 seen[seen.length - k](注意這邊都預設陣列的索引值從 0 開始數)。這樣一來每一次放新的元素進去平均都是常數時間。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。