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

74个回答

添加回答
推荐
    /**
     * 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 回复(77)
# -*- coding:utf-8 -*-
class Solution:
def reOrderArray(self, array):
# write code here
len1=[]
len2=[]
for i in array:
if i%2 == 0:
len1.append(i)
else:
len2.append(i)
return len2+len1
编辑于 2019-05-12 15:20:37 回复(0)
# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        n=len(array)
        list1=[]
        list2=[]
        list3=[]
        for i in range(n):
            if array[i]%2==0:
                list1.append(array[i])
            else:
                list2.append(array[i])
        #list3=list3.append(list1,list2)
        list2.extend(list1)
        return list2
发表于 2019-04-29 23:19:59 回复(0)

思路1:空间换时间

class Solution:
    def reOrderArray(self, array):
        array1 = []
        array2 = []
        i = 0
        for item in array:
            if item%2 == 0:
                array2.append(item)
            else:
                array1.append(item)
        array1.extend(array2)
        return  array1

思路2:

计数已经排序好的奇数个数,每次遇到新的奇数,就顺序调整到已排序的奇数的后一位
(顺序调整保证稳定性)

class Solution:
    def reOrderArray(self, array):
        k = 0 #前面排序好的奇数个数
        for i in range(len(array)):
            if array[i] % 2 == 1:
                j = i
                #逐个顺序调换,直到遇到已经排序好的奇数为止
                while j > k:
                    tmp = array[j-1]
                    array[j-1] = array[j]
                    array[j] = tmp
                    j-=1
                k+=1 #奇数个数+1
        return array
编辑于 2019-04-18 22:17:44 回复(0)
# -*- coding:utf-8 -*-
"""
方法1:时间复杂度O(n),空间复杂度O(n)
    利用一个新数组copy保存array的值,统计copy中奇数的个数
    然后在array前count_odd项保存奇数,后面的保存偶数
方法2:平均/最坏时间复杂度O(nlogn),最好时间复杂度O(n),最大空间复杂度O(n/2)
    利用python内置函数sort,其内部实现是Timsort
    Tim排序是稳定的,能保持相对位置不变,且具有适应性,最佳时间复杂度O(n)
    也就是在最好的情况下,时间复杂度和方法1一样,空间复杂度比方法1小一半(虽然同O(n))
其它方法:
    例如:冒泡、插入具有稳定性,空间复杂度O(1),但时间复杂度O(n^2)
    堆排序具有稳定性,但是时间复杂度O(nlogn),空间复杂度O(n),不如方法1和方法2
"""
class Solution:
    def reOrderArray(self, array):
        # write code here
        
        #方法1
        """
        count_odd = 0
        copy=[0]*len(array)
        for i in range(len(array)):
            copy[i] = array[i]
            if copy[i] & 1:
                count_odd += 1
        i, j = 0,count_odd
        for ch in copy:
            if ch & 1:
                array[i] = ch
                i += 1
            else:
                array[j] = ch
                j += 1
        return array 
    """
        #方法2:python内置sorted函数(Timsort)
        array.sort(key =lambda x: x%2==0)
        return array


发表于 2019-04-18 21:58:02 回复(0)
1 类似插入排序
# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        length=len(array)
        for i in range(1,length):
            if array[i]%2==1:
                for j in range(i,0,-1):
                    if array[j-1]%2==0:
                        tmp=array[j-1]
                        array[j-1]=array[j]
                        array[j]=tmp
                    else:
                        break
        return array
2 类似冒泡
# -*- coding:utf-8 -*-
classSolution:
        # write code here
        length=len(array)
        for i in range(0,length-1):
            for j in range(0,length-i-1):
                if array[j]%2==0 and array[j+1]%2==1:
                    tmp=array[j+1]
                    array[j+1]=array[j]
                    array[j]=tmp
        return array


发表于 2019-04-12 20:07:46 回复(0)
还用到了list的拼接
# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        left = []
        right = []
        for i in range(len(array)):
            if array[i] % 2 == 1:
                left.append(array[i])
            else:
                right.append(array[i])
        return left + right

编辑于 2019-04-09 22:48:12 回复(0)
python3  空间O(N)
class Solution:
    def reOrderArray(self, array):
        # write code here
        even,odd=[],[]
        for item in array:
            if item%2:
                odd.append(item)
            else:
                even.append(item)
        return odd+even 

发表于 2019-03-22 21:32:08 回复(0)

思路:将array从头到尾遍历,碰到偶数就放在oushu这个列表中
碰到奇数就放到jishu这个列表中,这样的话相对位置也并没有改变,因为是从前往后遍历原数组元素,
而每个元素被判断后也直接加到jishu或者oushu的后面。最后返回的时候把jishu和oushu合并,注意前后顺序即可。

class Solution:
def reOrderArray(self, array):
 #write code here      
    jishu = []
    oushu = []
    result = []
    for i in range(len(array)):
        if array[i]%2 == 0: 
            # 取余,为0说明是偶数
            oushu.append(array[i])
        else:
            jishu.append(array[i])
    result = jishu + oushu 
    return result

发表于 2019-03-21 20:58:44 回复(0)

快排的思路,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)