剑指Offer | 调整数组顺序使奇数位于偶数前面(二)

秦怀杂货店

发布于 2022-02-15 15:05:25

4010

Part0前言

剑指Offer & LeetCode刷题仓库：https://github.com/Damaer/CodeSolution 文档地址：https://damaer.github.io/CodeSolution/ 刷题仓库介绍：刷题仓库：CodeSolution 编程知识库：https://github.com/Damaer/Coding 文档地址：https://damaer.github.io/Coding/#/ 剑指OfferV1 系列已经完成，补增 V2 题目以及C++语言解法，欢迎关注~ 数据结构大总结：万字长文带你漫游数据结构世界

Part181.调整数组顺序使奇数位于偶数前面(二)

1题目描述

输入一个长度为 n 整数数组，数组里面可能含有相同的元素，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，对奇数和奇数，偶数和偶数之间的相对位置不做要求，但是时间复杂度和空间复杂度必须如下要求。

数据范围：0 ≤ n ≤ 50000，数组中每个数的值 0 ≤ val ≤ 10000 要求：时间复杂度 O(n)，空间复杂度 O(1)

示例 1

输入：[1,2,3,4]
返回值：[1,3,2,4]
说明：[3,1,2,4]或者[3,1,4,2]也是正确答案

示例 2

输入：[1,3,5,6,7]
返回值：[1,3,5,7,6]
说明：[3,1,5,7,6]等也是正确答案

2思路 & 解答

这道题只需要奇数在一半，偶数在另外一半就可以，并没有要求他们之间的顺序，那么我们就可以用双指针，一个指针在左边，一个指针在右边，比如1,3,5,6,7:

左指针往右遍历直到找到偶数，也就是 6 停下来，右指针往左走，直到找到第一个奇数，也就是 7 停下来。

两者交换:

左指针继续往右边走，两个指针相遇，结束，这个时候其实偶数已经全部在右边了。

这个例子里面只经过一次交换，如果是多次交换，那么结束的条件同样也是两个指针相遇。

Java代码实现如下：

public class Solution81 {
    public int[] reOrderArrayTwo(int[] array) {
        int low = 0;
        int high = array.length - 1;
        // 直到两个指针相遇
        while (low < high) {
            // 左指针往右查找偶数停下来
            while (array[low] % 2 == 1) ++low;
            // 右指针往左查找奇数停下来
            while (array[high] % 2 == 0) --high;
            if (low < high) {
                // 交换
                int temp = array[low];
                array[low] = array[high];
                array[high] = temp;
            }
        }
        return array;
    }
}

C++ 代码如下：

class Solution {
public:
    vector<int> reOrderArrayTwo(vector<int> &array) {
        int low = 0;
        int high = array.size() - 1;
        // 直到两个指针相遇
        while (low < high) {
            // 左指针往右查找偶数停下来
            while (array[low] % 2 == 1) ++low;
            // 右指针往左查找奇数停下来
            while (array[high] % 2 == 0) --high;
            if (low < high) {
                // 交换
                int temp = array[low];
                array[low] = array[high];
                array[high] = temp;
            }
        }
        return array;
    }
};

由于只查找了一遍数组，那么时间复杂度为 O(n),没有借助额外的空间，所以空间复杂度为 O(1)

【作者简介】

秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使缓慢，驰而不息。个人网站：http://aphysia.cn ,关注我，我们一起成长吧~

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2022-01-13，如有侵权请联系 cloudcommunity@tencent.com 删除

https