首页 > 试题广场 >

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

[编程题]调整数组顺序使奇数位于偶数前面
  • 热度指数:886995 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。
推荐
    /**
     * 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
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)
# -*- 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数组中有个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)
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)

方法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)
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)
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能用一行坚决不用两行的原则:
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)
# -*- 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)
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  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)
# -*- 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)
傻瓜方法:
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)
建立奇数列表,把原列表的奇数判断然后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)
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)
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)
  • 空间换时间
  • 保持相对顺序
# -*- 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实现)

1.理论

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

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

解题思路

  1. 删除与添加的方式
    思路:当元素是奇数,指针i前进一步,即i++,不做其他处理;当元素是偶数,删除当前位置的偶数,并将当前的偶数添加到数组的末尾,同时数组的长度n减一,即n--(是为防止添加到数组末尾的偶数再次被处理),具体实现情况代码method 1。T(n)=o(n)、S(n)=o(1)。

  2. 使用两个队列分别存储奇数、偶数,之后再合并两个队列。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)
# -*- 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)