面试题21. 调整数组顺序使奇数位于偶数前面

调整数组顺序使奇数位于偶数前面

题目描述

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分

示例：

输入：nums = [1,2,3,4]
输出：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一。

提示：
1 <= nums.length <= 50000
1 <= nums[i] <= 10000

转载来源：力扣（LeetCode）

题目分析

又是双指针的题，头指针一开始指向数组头，尾指针一开始指向数组尾，从两头往中间逼进；

• 如果头指针指向的数是奇数，那么它和它之前的数都是奇数，是有序的，头指针往后移；
• 如果尾指针指向的数是偶数，那么它和它之后的数都是偶数，是无序的，尾指针往前移；
• 如果头指针不往后移，尾指针都不往前移，那就是说头指针不是奇数，尾指针不是偶数，将它们交换一下不就头奇尾偶了吗？然后同时将两个指针前或后的数都变成符合题意的，nice！这是头指针往后移，尾指针往前移，继续整理，知道把整个数组都遍历了；

思路就是上面那样啦，只用遍历一遍数组就能整理完毕，时间复杂度就是O(N)。

fun exchange(nums: IntArray): IntArray {
        var head = 0
        var tail = nums.size - 1
        while(head < tail){
            if(nums[head] % 2 == 1){
                head++
                continue
            }
            if(nums[tail] % 2 == 0){
                tail--
                continue
            }
            val tmp = nums[head]
            nums[head] = nums[tail]
            nums[tail] = tmp
            head++
            tail--
        }
        return nums
    }

代码文件