[Go的算法实现]调整数组顺序使奇数位于偶数前面
Publish date: Aug 2, 2019
Last updated: Jun 14, 2020
Last updated: Jun 14, 2020
剑指Offer中问题14的go实现。
问题
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。
思路
使用冒泡法可以解决问题,且能保证顺序不变,但是计算复杂度略高。
为减少复杂度可以使用两个指针从前后分别开始向中间靠拢,一旦发现偶数在奇数的前面就交换两个数字的位置,不过这种方法会影响数字之间的相对位置。
注意点
- 空数组
- 全偶/奇数组
代码实现
package q014
func AnswerBubble(inputList []int) (outputList []int) {
head := 0
tail := len(inputList) - 1
for head <= tail {
for inputList[head]%2 == 1 && head <= tail {
head++
}
for i, j := head, head+1; j < len(inputList) && head <= tail; {
inputList[i], inputList[j] = inputList[j], inputList[i]
i++
j++
}
tail--
}
return inputList
}
func AnswerTwoPointer(inputList []int) (outputList []int) {
head := 1
tail := len(inputList) - 1
for head < tail {
for inputList[head]%2 == 1 && head < tail {
head++
}
for inputList[tail]%2 == 0 && head < tail {
tail--
}
inputList[head], inputList[tail] = inputList[tail], inputList[head]
}
return inputList
}