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

2021-03-03 22:29

阅读：341

标签：com ase turn info 位置 fast 没有 offer ++

技术图片

这道题要求将数组中奇数放前面偶数放后面，不需要排序。

第一时间想到的是额外数组res存结果，遍历原数组奇数存在res前面，偶数存在res后面。

时间复杂度O（n），空间复杂度O（n），好处是没有修改原数组

class Solution {
    public int[] exchange(int[] nums) {
        if (nums.length)
        {
            return nums;
        }
        int i=0,j=nums.length-1;
        int[] res = new int [nums.length];
        for(int num:nums)
        {
            if (num%2==1)
                res[i++]=num;
            else
                res[j--]=num;
        }
        return res;
    }
}

在此之后发现可以不用额外数组，采用双指针在原数组上改动，降低空间复杂度。

采用首尾双指针，头指针右移，尾指针左移；

头指针遇到偶数或尾指针遇到奇数，则二者指向数组元素交换，直至头尾指针相遇。

时间复杂度O（n），空间复杂度O（1）

class Solution {
    public int[] exchange(int[] nums) {
        int i=0, j=nums.length-1, tmp;
        while(i  j) 
        {
            while(i ;
            while(i ;
            tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
        return nums;
    }
}

做完看题解发现也可以用快慢双指针解题。快慢指针都从数组头开始遍历。

快指针fast的作用是向前搜索奇数位置，慢指针low的作用是指向下一个奇数应当存放的位置。

fast 向前移动，当它搜索到奇数时，将它和 nums[low]交换，此时 low向前移动一个位置。重复，直到 fast指向数组末尾。

时间复杂度O（n），空间复杂度O（1）

class Solution {
    public int[] exchange(int[] nums) {
        int i=0, j=0, tmp;
        for(i=0;i) 
        {
            if (nums[i]%2==1)
            {
                tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
                j++;
            }
        }
        return nums;
    }
}

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

标签：com ase turn info 位置 fast 没有 offer ++

原文地址：https://www.cnblogs.com/zccfrancis/p/14381658.html

上一篇：Spring Boot 配置文件

下一篇：对图像进行SVD和PCA降维，可用于压缩或者图像数据增强(python版)

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
文章链接：http://soscw.com/index.php/essay/59717.html

亲，登录后才可以留言！

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

评论

热门文章

推荐文章

最新文章

置顶文章