剑指Offer（十三）：调整数组顺序使奇数位于偶数前面

2017年11月30日12:19:53 5 5,960 °C
摘要

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

剑指Offer（十三）：调整数组顺序使奇数位于偶数前面

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台：牛客网

书籍下载：共享资源

二、题目

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

1、思路

创建双向队列，遍历数组，奇数前插入，偶数后插入。最后使用assign方法实现不同容器但相容的类型赋值。

2、代码

C++：

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    void reOrderArray(vector<int> &array) {
        deque<int> result;
        int num = array.size();
        for(int i = 0; i < num; i++){
            if(array[num - i - 1] % 2 == 1){
                result.push_front(array[num - i - 1]);
            }
            if(array[i] % 2 == 0){
                result.push_back(array[i]);
            }
        }
        array.assign(result.begin(),result.end());
    }
};

Python2.7：

双向队列：

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
# -*- coding:utf-8 -*-
from collections import deque
class Solution:
    def reOrderArray(self, array):
        # write code here
        odd = deque()
        l = len(array)
        for i in range(l):
            if array[l-i-1] % 2 != 0:
                odd.appendleft(array[-i-1])
            if array[i] % 2 == 0:
                odd.append(array[i])
        return list(odd)

列表：

Python
1
2
3
4
5
6
7
8
9
10
11
12
# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        res = []
        l = len(array)
        for i in range(l):
            if array[l-i-1] % 2 != 0:
                res.insert(0,array[-i-1])
            if array[i] % 2 == 0:
                res.append(array[i])
        return res

不开辟新空间：

Python
1
2
3
4
5
6
7
8
9
10
# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        boarder = -1
        for idx in range(len(array)):
            if array[idx] % 2:
                boarder += 1
                array.insert(boarder, array.pop(idx))
        return array

 

weinxin
微信公众号
分享技术，乐享生活：微信公众号搜索「JackCui-AI」关注一个在互联网摸爬滚打的潜行者。
Jack Cui

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论：5   其中：访客  3   博主  2

    • avatar 发文 未知系统 谷歌浏览器 Windows 10 局域网 对方和您在同一内部网 4
      回复 2018年7月20日 上午11:16  沙发

      c.assign(beg,end)：将[beg; end)区间中的数据赋值给c。

      • avatar 董明高 来自天朝的朋友 谷歌浏览器 Windows 10 北京市 电信互联网数据中心 1
        回复 2019年3月20日 下午4:20  板凳

        这道题如果不借助辅助队列，使用插入排序是不是更好：
        void reOrderArray(int arr[], int len) {
        for (int i = 0; i 0; j–) {
        if (arr[j-1]%2 == 1)
        break;

        int tmp = arr[j-1];
        arr[j-1] = arr[j];
        arr[j] = tmp;
        }
        }
        }

          • avatar Jack Cui Admin 来自天朝的朋友 Safari浏览器 Mac OS X 10_14_3 北京市 百度网讯科技联通节点
            回复 2019年3月20日 下午8:30  1层

            @董明高 :wink: :wink: :wink: :wink:

              • avatar 董明高 来自天朝的朋友 谷歌浏览器 Windows 10 北京市 电信互联网数据中心 1
                回复 2019年3月20日 下午8:32  2层

                @Jack Cui 哈哈，我贴的代码不知道为什么不能正常显示

                  • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 10 北京市 联通
                    回复 2019年3月20日 下午10:16  3层

                    @董明高 正常留言区我没有设置代码样式。