剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

题目说明

  1. 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，
  2. 所有偶数位于数组的后半部分。
  3. 示例：
  5. 输入：nums = [1,2,3,4]
  6. 输出：[1,3,2,4] 
  7. 注：[3,1,2,4] 也是正确的答案之一。
  10. 提示：
  12. 1 <= nums.length <= 50000
  13. 1 <= nums[i] <= 10000

题解

方法一：简单但是不优雅的解法

主要解题思路是

  • 新建两个数组
  • 遍历，进行元素奇偶划分
  • 合并两个数组

如果你用这种解法，面试估计凉凉，空间复杂度比较高
image.png

func exchange(nums []int) []int {
    a := []int{}
    b := []int{}

    for _,num :=range nums{
        if num % 2==0{
            a = append(a, num)
        }else{
            b = append(b, num)
        }
    }

    return append(b,a...)
}

方法二：双指针遍历元素置换

image.png
执行时间微小提高，内存消耗依旧很大

func exchange(nums []int) []int {
    head := 0
    tail := len(nums)-1

    for head< tail{
        for nums[head]%2!=0{ // 前面是奇数
            if head < tail{
                head++
            }else {
                break
            }
        }
        for nums[tail]%2 ==0{ // 后面是偶数
            if head < tail{
                tail--
            }else {
                break
            }
        }
        nums[head],nums[tail] = nums[tail],nums[head]
    }

    return nums
}

内存消耗依旧很高，看了一下官网给出的最优的内存，也差不了多少….那还不如用方法一呢，哈哈哈
image.png