首页 > 试题广场 > 调整数组顺序使奇数位于偶数前面
[编程题]调整数组顺序使奇数位于偶数前面
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。

65个回答

添加回答
推荐
    /**
     * 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 回复(71)

快排的思路,O(n):

# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, A):
        # write code here
        i = -1 ##采用快排的思路。保证>=i的元素为奇数,[i+1,j-1]为偶数,遇到奇数时,与i+1的元素对调,即可。
        j = 0
        while j < len(A):
            if A[j] & 0x01:
                A[i+1], A[j] = A[j], A[i+1]
                i += 1
                j += 1
            else:               
                j += 1
        A[i+1:]= sorted(A[i+1:])#其实题意并没要求有序
        return A
发表于 2019-03-20 17:48:17 回复(0)
# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        uneven = []
        even = []
        for i in array:
            if i % 2 == 0:
                even.append(i)
            else: uneven.append(i)
        return uneven + even
发表于 2019-03-20 15:18:00 回复(0)
 def reOrderArray(self, array):
        result=[]
        result1=[]
        result2=[]
        for i in range(len(array)):
            if array[i]%2==1:
                result1.append(array[i])
            else:
                result2.append(array[i])
        result=result1+result2
        return result
发表于 2019-03-08 14:17:03 回复(0)
# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        array_head = []
        array_tail = []
        for i in range(0,len(array)):
            if array[i]%2 == 0:#偶数
                array_tail.append(array[i])
            else:
                array_head.append(array[i])
        return array_head+array_tail

发表于 2019-03-05 09:40:49 回复(0)
# 往前移就行,重点是考虑以时间换空间。空间复杂度为O(1),时间复杂度为最差为O(n2)
class Solution:
    def reOrderArray(self, arr):
        # write code here
        last = len(arr) - 1  
        first = len(arr) - 1  
        while first >= 0 and last >= 0:
            while last >= 0 and not(arr[last] & 0x01):  # 指向前一个奇数
                last -= 1
            if first > last:  # first的偶数只能在last的前边
                first = last    
            while first >= 0 and (arr[first] & 0x01):  # 指向前一个偶数
                first -= 1

            if first >= 0 and last >= 0:
                for i in range(last - first):
                    temp = arr[first+i]
                    arr[first+i] = arr[first+i+1]
                    arr[first+i+1] = temp
        return arr
发表于 2019-03-02 22:22:15 回复(0)
class Solution:
    def reOrderArray(self, array):
        # write code here
        if not array:
            return []
        odd = []
        even = []
        for i in array:
            if i % 2 == 1:      odd.extend([i])
            else:
                even.extend([i])
    return odd + even
      # return odd.extend(even) 会报错 [object of type 'NoneType' has no len() 
用一个很平凡的方法做出来了,想请教一下各位,为什么下面那种方法会报错呢?在本地能够通过呀……
发表于 2019-02-10 10:37:12 回复(0)
         j = [n for n in array if n%2!=0]
        o = [n for n in array if n%2==0]
        return j+o

发表于 2018-11-01 16:34:53 回复(0)
# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        list=[]
        list1=[]
        for arr in array:
            if arr%2!=0:
                list.append(arr)
            else:
                list1.append(arr)
        list.extend(list1)
        return list

发表于 2018-09-07 14:59:23 回复(1)
# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        odd_lst=[x for x in array if x%2==1]
        return odd_lst+[x for x in array if x not in odd_lst]

发表于 2018-09-06 16:18:35 回复(0)
法一:时间复杂度O(n^2)
# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        s = list(array)
        n = len(array)
        m = 0
        for j in range(0,n-1):
            for i in range(0,n-1):
                if s[i]%2 ==0 and s[i+1]%2 ==1:
                    m = s[i]
                    s[i] = s[i+1]
                    s[i+1] = m
        return s
法二:时间复杂度 O(2*n)

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

发表于 2018-09-01 19:40:40 回复(0)
法1:
class Solution:

    def reOrderArray(self, array):

        lst = []

        lens = len(array)

       

        i = 0

        #不用array[i]或者range(len(array))遍历。改为:lens次循环,即lens次遍历

        while lens > 0:   

            if array[i] % 2 == 0:

                #如果是偶数,array删除元素后,i游标不向后移动。

                lst.append(array[i])

                array.remove(array[i])

            else:

                #如果是奇数,i游标向后移动。

                i += 1

            lens -= 1

                   

        print(array + lst)

        return array + lst

法2:

class Solution:

    def reOrderArray(self, array):

        import copy

        array_copy = copy.deepcopy(array)   #重点:对array深拷贝,得到的array_copy有自己的指针,不受array变化的影响

        lst = []

   

        for i in array_copy:      #遍历备份array_copy的元素,删除array中的元素

            if i % 2 == 0:        #偶数

                lst.append(i)     #发现的偶数放进lst

                array.remove(i)   #删掉array中的偶数

        print(array + lst)

        return array + lst

  

array = [2,4,6,1,3,5,7]

result = Solution()

result.reOrderArray(array)


发表于 2018-08-29 15:00:16 回复(0)
class Solution:
    def reOrderArray(self, array):
        # write code here
        ou=[]
        ji=[]
        for i in range(len(array)):
            if array[i]%2==0:
                ou.append(array[i])
            else:
                ji.append(array[i])
        return ji+ou
发表于 2018-08-27 22:47:31 回复(0)
class Solution:   def reOrderArray(self, array):         even = []         odd = []         for i in array:             if i%2==0:                 even.append(i)             else:                 odd.append(i)         return odd+even
   
发表于 2018-08-27 00:32:15 回复(0)
让一让,python大法来了
#一行代码:
return sorted(array, key = lambda i: i%2, reverse = True )
#四行代码1:
arr1 = [i%2 for i in array]
arr2 = [i*j for i,j in zip(arr1,array) if i!=0]
arr3 = [(1-i)*j for i,j in zip(arr1,array) if i!=1]
return arr2+arr3
#四行代码2:
odd,even=[],[]
for i in array:
    odd.append(i) if i%2==1 else even.append(i)
return odd+even

编辑于 2018-08-15 20:23:06 回复(0)
# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        record=0
        longth=len(array)
        for i in range(0,longth):
            if array[i]%2==1:
                if i>record:
                    mid=array[i]
                    for j in reversed(range(record,i)):
                        array[j+1]=array[j]
                    array[record]=mid
                    record+=1
                else:
                    record+=1
        return array

发表于 2018-08-05 11:33:03 回复(0)
简单易懂的python一行解法:
        return [e for e in array if e%2==1]+[e for e in array if e%2!=1]

发表于 2018-08-01 15:25:38 回复(0)

python

# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        if len(array)==1 or len(array)==0:
            return array
        for i in range(len(array)):
            if array[i]%2==1:
                return [array[i]]+self.reOrderArray(array[i+1:len(array)])
            elif array[i]%2==0:
                for j in range(i+1,len(array)):
                    if  array[j]%2==1:
                        for k in range(j,i,-1):
                            array[k],array[k-1]=array[k-1],array[k]
                        return [array[i]]+self.reOrderArray(array[i+1:len(array)])
                    else:
                        continue
                return array
发表于 2018-06-28 15:37:51 回复(0)
python 数组重构解法:
    def reOrderArray(self, array):
        # write code here
        oarray=[]
        earray=[]
        for a in array:
            if a%2==0:
                earray.append(a)
            else: oarray.append(a)
        c=oarray+earray
        return c

编辑于 2018-05-29 16:12:06 回复(0)
我感觉时间复杂度o(n/2),不知道是不是想错了
# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        if array==None :
            return None
        if len(array)==1or len(array)==0:
            return array
        length=len(array)//2
        i=0
        while  i<=length:
            if array[i]%2==0:
                temp=array.pop(i)
                array.append(temp)
                i-=1
            i+=1
        return array
发表于 2018-05-16 22:10:55 回复(0)

'''
思路是创建两个列表奇偶存起来然后合并即可
'''

class Solution:
    def reOrderArray(self, array):
        # write code here
        
        left = [x for x in array if x & 1]
        right = [x for x in array if not x & 1]
        return left + right

    

编辑于 2018-05-11 01:31:23 回复(0)

扫一扫,把题目装进口袋

牛客网,程序员必备求职神器

扫描二维码,进入QQ群

扫描二维码,关注牛客网公众号

  • 公司地址:北京市朝阳区大屯路东金泉时代3-2708北京牛客科技有限公司
  • 联系方式:010-60728802(电话) admin@nowcoder.com
  • 牛客科技©2018 All rights reserved
  • 京ICP备14055008号-4
  • 京公网安备 11010502036488号