這裡給了兩個 Solution,第一個是用兩個指針去變歷整個陣列,用一個 bool 來做為判斷正負數的狀態,當遇到正數時, 就把它放到 result 陣列中,然後把狀態改變,讓下一個數字是負數,反之亦然。
這個解法的 Time Complexity 是 O(n*2),因為我們要去找正數和負數的 index所以相當於走了兩次迴圈。
Solution 1:
func rearrangeArray(nums []int) []int {
var result []int
var status bool = true
var i, j int = 0, 0
for p := 0; p < len(nums); p++ {
if status {
for i < len(nums) && nums[i] < 0 {
i++
}
result = append(result, nums[i])
status = !status
i++
} else {
for j < len(nums) && nums[j] > 0 {
j++
}
result = append(result, nums[j])
status = !status
j++
}
}
return result
}
第二個解法是用兩個指針,一個是負數的指針,一個是正數的指針,這裡我們去觀察題目:
- 如果是正數他的 index 絕對是 even
- 如果是負數他的 index 絕對是 odd 既然我們已經知道這個規則那麼用一個 for loop 就可以解決這個問題了,遇到正數就放到 even index,遇到負數就放到 odd index。
這樣 Time Complexity 就會是 O(n)。
Solution 2:
func rearrangeArray(nums []int) []int {
result := make([]int, len(nums))
pos, neg := 0, 1
for _, v := range nums {
if v > 0 {
result[pos] = v
pos += 2
} else {
result[neg] = v
neg += 2
}
}
return result
}