首页 > 试题广场 >

调整数组顺序使奇数位于偶数前面

[编程题]调整数组顺序使奇数位于偶数前面

热度指数：887021 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

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

算法知识视频讲解

推荐

nailperry

    /**
     * 1.要想保证原有次序，则只能顺次移动或相邻交换。
     * 2.i从左向右遍历，找到第一个偶数。
     * 3.j从i+1开始向后找，直到找到第一个奇数。
     * 4.将[i,...,j-1]的元素整体后移一位，最后将找到的奇数放入i位置，然后i++。
     * 5.終止條件：j向後遍歷查找失敗。
     */
    public void reOrderArray2(int [] a) {
    	if(a==null||a.length==0)
    		return;
        int i = 0,j;
        while(i<a.length){
        	while(i<a.length&&!isEven(a[i]))
        		i++;
        	j = i+1;
        	while(j<a.length&&isEven(a[j]))
        		j++;
        	if(j<a.length){
        		int tmp = a[j];
        		for (int j2 = j-1; j2 >=i; j2--) {
					a[j2+1] = a[j2];
				}
        		a[i++] = tmp;
        	}else{// 查找失敗
        		break;
        	}
        }
    }
    boolean isEven(int n){
    	if(n%2==0)
    		return true;
    	return false;
    }

编辑于 2015-08-18 23:19:51 回复(102)

Python

611的

人生苦短，我用python

python一行代码

return [i for i in array if i%2==1]+[i for i in array if i%2==0]

发表于 2021-01-25 10:29:03 回复(0)

Python

牛客89482527号

# -*- coding:utf-8 -*-
class Solution:
def reOrderArray(self, array):
if not array:
return []

#从前往后遍历，当遇到奇数时，把该奇数前的偶数往后移一位，然后奇数往前放
for i in range(len(array)):
if array[i]%2==1:
tmp = array[i]
j=i-1
while j>=0:
if array[j]%2==0:
array[j+1]=array[j]
j -= 1
else:
break
array[j+1]=tmp

return array

发表于 2021-01-03 20:45:21 回复(0)

Python

Bogerhummer

Python数组中有个pop和append,所以在从前往后遍历的时候遇到偶数就先pop掉然后再加入到数组得末尾，这样一次遍历而且还不需要遍历到整个数组就能完成，代码如下啊：

class Solution:
def reOrderArray(self , array ):
# write code here
t = len(array)-1
i = 0
while (i <= t):
if array[i] % 2 == 0:
temp = array[i]
array.pop(i)
array.append(temp)
t-=1
else:
i += 1
return array

发表于 2020-12-31 16:14:13 回复(0)

Python

MayaAyaya

n = len(array)
i,count = 0,0
while count < n :
    if array[i] % 2 == 0:
        array.append(array[i])
        del(array[i])
    else:
        i+=1
    count+=1

双指针线下测试就c，提交就数据格式报错，是py2.7.3的锅？

发表于 2020-11-25 12:01:40 回复(0)

Python

BJ-2020

方法1：用一个数组，循环两次

class Solution:
    def reOrderArray(self, array):
        # write code here
        if array == None:
            return array
        ret = []
        for i in range(len(array)):
            if array[i] % 2 == 1:
                ret.append(array[i])
        for i in range(len(array)):
            if array[i] % 2 == 0:
                ret.append(array[i])
        return ret

2.用两个数组

class Solution:
    def reOrderArray(self, array):
        # write code here
        if array == None:
            return array
        x = []
        y = []
        for i in range(len(array)):
            if array[i] % 2 == 1:
                x.append(array[i])
            if array[i] % 2 == 0:
                y.append(array[i])
        return x+y

3.冒泡法
前后奇数偶数调换位置
每次确定最后一个数，所以是n-i-1

class Solution:
    def reOrderArray(self, array):
        # write code here
        if array == None:
            return array
        for i in range(len(array)-1):
            for j in range(len(array)-i-1):
                if array[j] % 2 == 0 and array[j + 1] % 2 == 1:
                    array[j], array[j+1] = array[j+1],array[j]
        return array

发表于 2020-09-06 00:41:35 回复(0)

Python

苏堤牧

class Solution:
    def reOrderArray(self, array):
        first = None
        index = 0
        while index < len(array):
            if not array[index] % 2:
                temp = array[index]
                if first == temp:
                    return array
                if first is None:
                    first = temp
                array.append(temp)
                array.pop(index)
            else:
                index += 1
        return array

编辑于 2020-09-03 21:30:24 回复(0)

Python

Yvette_ZYH

python3 解法

看了其他小伙伴的python解法，几乎都是再额外动用两个列表空间进行处理，

于是在想能不能直接在原数组空间基础上操作呢？

答案是，可以！以下附代码，已通过样例，但不知道有没有其他牛客网未检出的细节问题，

还望各位大神指正~！

class Solution:
    def reOrderArray(self, array):
        lon = len(array)
        i = 0
        count = 0  #为了统计我们判断的次数
        while count < lon:
            # 如果是偶数，直接接在array末尾，下一个判断数的下标仍为i
            if array[i] % 2 == 0:
                array.append(array.pop(i))
            # 如果是奇数，停在原位置，从下一个位置i+1判断
            else:
                i += 1
            # 无论是奇是偶，判断1次，count则加1
            count += 1
        return array

发表于 2020-08-19 17:38:59 回复(0)

Python

努力搬砖的小王

本着python能用一行坚决不用两行的原则：

class Solution:
    def reOrderArray(self, array):
        # write code here
        return [i for i in array if i%2==1] + [i for i in array if i%2==0]

ps：上述的解法时间和空间复杂度都是O(n)

发表于 2020-07-31 22:28:38 回复(0)

Python

DDooo

# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        list1 = []
        list2 = []
        for i in array:
            if i % 2 == 1:
                list1.append(i)
            elif i % 2 == 0:
                list2.append(i)
        for j in list2:
            list1.append(j)
        return list1

很久没刷题了，今天在array index这里出了点错花了不少时间，第二个是append的用法，注意细节：

比如：

list1 =[0,9]
print(list1.append(5))

就会出错，输出None；

而正确做法应该是：

list1 =[0,9]
list1.append(5)
print(list1)

输出：[1,9,5]

发表于 2020-07-29 16:45:04 回复(0)

Python

善良的肉肉菌

class Solution:
    def reOrderArray(self, array):
            # write code here
        j=i=0
        while j<len(array):
            if array[i]%2 == 0:
                array.append(array[i])
                array.pop(i)
                j=j+1
            else:
                i = i+1
                j=j+1
        return array

j用来判断到没到结尾，i指向当前位置；

如果是偶数，append添加到最后，并且pop删除这个数；

如果是奇数，直接指向下一个数；

发表于 2020-07-04 14:11:41 回复(0)

Python

橘子汽水超人2号

Python Solution

return [x for x in array if x&1==1] + [x for x in array if x&1==0]

编辑于 2020-05-31 15:17:17 回复(0)

Python

一直爬的蜗牛

# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        odd, even = [], []
        for i in array:
            if i % 2 == 0:
                odd.append(i)
            else:
                even.append(i)
        return even + odd

发表于 2020-05-23 01:52:14 回复(0)

Python

Chloe_y

傻瓜方法：

class Solution:

def reOrderArray(self, array):
# write code here
list1=[]
list2=[]
for i in range(len(array)):
if array[i]%2 ==1:
list1.append(array[i])
if array[i]%2==0:
list2.append(array[i])
list = list1+list2
return list

发表于 2020-05-19 20:46:11 回复(0)

Python

琴音凝韵

建立奇数列表，把原列表的奇数判断然后pop出来append到奇数列表，然后相加奇数列表和原列表（偶数列表）

class Solution:
    def reOrderArray(self, array):
        i = 0
        jishuList = []

        while i < len(array):

            if array[i]%2 == 1:
jishuList.append(array.pop(i))

            else:
i += 1

        arrayList = jishuList+array
        return arrayList

发表于 2020-03-26 16:43:32 回复(0)

Python

step8istep

class Solution:
    def reOrderArray(self, array):
        odd_arr = []
        even_arr = []
        for element in array:
            if element%2==1:
               odd_arr.append(element)
            else:
                even_arr.append(element)
        odd_arr.extend(even_arr)
        return odd_arr

发表于 2020-03-23 20:48:32 回复(0)

Python

llfgo4it

class Solution:
    def reOrderArray(self, array):
        # write code here
        (742)# we generate a new array
        new = [0 for i in range(len(array))]
        p , q = 0, len(array)-1
        i,j= p, q
        while i< len(array):
            if array[i]&0x1 ==1:
                new[p]= array[i]
                p+=1
            if array[j]&0x1 !=1:
                new[q]= array[j]
                q-=1
            i += 1
            j -= 1
        return new

借助了辅助空间，生成一个与原数组同长度的新数组。用4个指针i, j, p, q分别指向新老数组的首尾，i向右移，j向左移。i碰到奇数就加到新数组的头部（然后p++），j碰到偶数就添加到新数组尾部（然后q--），时间复杂度O(n)

发表于 2020-03-22 19:50:32 回复(0)

Python

牛客447097232号

空间换时间
保持相对顺序

# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        """
        与quick sort一致，但是这样相对顺序就打乱了
        :param array:
        :return:
        """

        if len(array) <= 1:
            return array
        else:
            pre = 0
            for j in range(1,len(array)):
                if array[j] % 2 == 1:
                    pre += 1
                    array[pre],array[j] = array[j],array[pre]
            array[pre],array[0] = array[0],array[pre]
            return array

    def reOrderKeepRelativePosition(self,array):
        res = [0 for i in range(len(array))]
        m = 0
        for i in range(len(array)):
            if array[i] %2 ==1:
                res[m] = array[i]
                m += 1
        n = len(array) - 1
        for i in range(len(array) - 1, -1, -1):
            if array[i] % 2 ==0:
                res[n] = array[i]
                n = n-1

        return res

s = Solution()
ans = s.reOrderKeepRelativePosition([1,2,22,3,5])
print(ans)

发表于 2020-02-26 23:50:35 回复(0)

Python

201905242154668

调整数组顺序(理论+python实现)

1.理论

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

题目的难点在于如何让奇数与奇数、偶数与偶数之间的相对位置不变

解题思路

删除与添加的方式
思路：当元素是奇数，指针i前进一步，即i++，不做其他处理；当元素是偶数，删除当前位置的偶数，并将当前的偶数添加到数组的末尾，同时数组的长度n减一，即n--（是为防止添加到数组末尾的偶数再次被处理），具体实现情况代码method 1。T(n)=o(n)、S(n)=o(1)。
使用两个队列分别存储奇数、偶数，之后再合并两个队列。T(n)=o(n)、S(n)=o(n)，要消耗多余的内存空间。

2.python实现

# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        #-----------------------
        #method 1
        #当元素是奇数，i++；当元素是偶数，添加偶数到数值末尾，并删除当前偶数，n--
        # T(n)=o(n),S(n)=o(1)
        n=len(array)
        i=0
        while i<n:
            if array[i]%2!=0:
                i+=1
            else:
                array.append(array[i])
                del array[i]
                n-=1
        return array

        #-----------------------
        #method 2
        #使用两个队列分别存储奇数、偶数，之后再合并两个队列
        #T(n)=o(n),S(n)=o(n)
        q1,q2=[],[]
        for i in range(len(array)):
            if array[i]%2!=0:
                q1.append(array[i])
            else:
                q2.append(array[i])
        q1.extend(q2)  #合并两个队列
        return q1

编辑于 2020-02-24 22:21:26 回复(0)

Python

烧腊小王子

# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        length1 = len(array)
        array1 = []
        array2 = []
        for i in range(length1):
            if (array[i]% 2) == 0:
                array2.append(array[i])
            else:
                array1.append(array[i])
        array1.extend(array2)
        return array1

开辟了两个数组空间，比较奢侈

一个专门放奇数一个专门放偶数，最后利用python自带的extend函数将两个数组合并返回即可

编辑于 2020-02-22 22:29:11 回复(0)

提交观点

问题信息

数组

来自：编程题练习卷

难度：

138条回答 1804收藏 302884浏览

通过挑战的用户

人来疯的伊登等...

2023-03-14 20:46:02
浪漫不死

2023-03-03 16:19:37
Elastic...

2023-02-27 10:19:34
日服男枪战绩可查

2023-02-24 17:50:25
牛客59897...

2023-02-13 11:22:24

调整数组顺序使奇数位于偶数前面

Python Solution

调整数组顺序(理论+python实现)

1.理论

2.python实现

问题信息

热门推荐

通过挑战的用户

相关试题