剑指Offer每日一题16、调整奇偶顺序

一、前言

大家好，本文章属于《剑指 Offer 每日一题》中的系列文章中的第 16 篇。

在该系列文章中我将通过刷题练手的方式来回顾一下数据结构与算法基础，同时也会通过博客的形式来分享自己的刷题历程。如果你刚好也有刷算法题的打算，可以互相鼓励学习。我的算法基础薄弱，希望通过这两三个月内的时间弥补这块的漏洞。本次使用的刷题语言为 Java ，预计后期刷第二遍的时候，会采用 Python 来完成。

• 刷题平台： leetcode 的剑指 Offer 专题
• 码云仓库地址

二、题目

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

示例1：

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

提示：

1. 0 <= nums.length <= 50000
2. 1 <= nums[i] <= 10000

三、解题

本题采用双指针的形式，新建一个等长度的空的数组和两个指针标识，一个指向数组的左侧，另一个指向数组的右侧，如果是奇数，就在左侧加入数组，然后左指针右移一位，如果是偶数，那么右指针左移一位，把元素加入数组。

3.1 代码

 static public int[] exchange(int[] nums) {
             int [] a=new int[nums.length];
             int length = nums.length;
             int j=0,k=0;
             for (int i = 0; i < length; i++) {
                 if(nums[i]%2!=0){
                     a[j++]=nums[i];
                 }else{
                     k++;
                     a[length-k]=nums[i];
                 }
             }
             return a;
         }
复制代码

3.2 执行效果

3.3 复杂度

• 时间复杂度 O（n）
• 空间复杂度 O（n）

四、小结

前面的两题太恶心了，跳到了这题，没头发刷题了，还是要从简单的题目找点信心。