剑指offer–21-调整数组顺序使奇数位于偶数前面

题目描述

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

示例：

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

思路一 ： 快慢指针

• 定义快慢指针，fast 和 low ,fast在前，low 在后
• fast的作用是向前搜索奇数的位置，low的作用是指向下一个奇数应该存放的位置
• fast 向前移动,当它搜索到奇数的时候，将它和nums[low] 进行交换，此时low 向前移动一个位置
• 重复上述操作，直到fast指向数组末尾

class Solution {
    public int[] exchange(int[] nums) {
        if(nums.length < 2){
            return nums;
        }
        // 1. 定义快慢指针
        int slow = 0;
        int fast = 0;
        // 2. 快慢指针遍历
        while(fast < nums.length){
            if((nums[fast] & 1) == 1){          // 如果nums[fast] 是奇数的话
                int temp = nums[fast];
                nums[fast] = nums[slow];
                nums[slow] = temp;
                slow++;                         // 交换完毕 slow++
            }
            fast++;
        }
        return nums;
    }

    // 交换函数
    public void swap(int x,int y){
        int temp = x;
        x = y;
        y = temp;
    }
}

复杂度分析

• 时间复杂度 : O(n) 遍历一遍数组
• 空间复杂度 ：O(1) 没有使用额外空间

打赏