首页 > 试题广场 >

仅用O(1)的空间，将整数数组按奇偶数分成2部分，数组左边是

[问答题]
仅用O(1)的空间，将整数数组按奇偶数分成2部分，数组左边是奇数、右边是偶数。（要求：给出完整代码，尽量高效，简洁）
添加回答
推荐
香蕉牛奶头像 香蕉牛奶
#两个指针，分别从头和从尾遍历数组，详见代码，已测试通过 
#include <stdio.h>
#include <stdlib.h>
#define bool int
#define false 0
#define true 1
void Reorder(int *pData, unsigned int length, bool (*func)(int));
bool isEven(int n);
void ReorderOddEven_1(int *pData, unsigned int length)
{
    if(pData == NULL || length == 0)
        return;
    int *pBegin = pData;
    int *pEnd = pData + length - 1;
    while(pBegin < pEnd)
    {
        // 向后移动pBegin，直到它指向偶数
        while(pBegin < pEnd && (*pBegin & 0x1) != 0)
            pBegin ++;
        // 向前移动pEnd，直到它指向奇数
        while(pBegin < pEnd && (*pEnd & 0x1) == 0)
            pEnd --;
        if(pBegin < pEnd)
        {
            int temp = *pBegin;
            *pBegin = *pEnd;
            *pEnd = temp;
        }
    }
}
void Reorder(int *pData, unsigned int length, bool
  (*func)(int))
{
    if(pData == NULL || length == 0)
        return;
    int *pBegin = pData;
    int *pEnd = pData + length - 1;
    while(pBegin < pEnd) 
    {
        //向后移动pBegin
        while(pBegin < pEnd &&!func(*pBegin))
            pBegin ++;
        // 向前移动pEnd
        while(pBegin < pEnd &&func(*pEnd))
            pEnd --;
        if(pBegin < pEnd)
        {
            int temp = *pBegin;
            *pBegin = *pEnd;
            *pEnd = temp;
        }
    }
}
bool isEven(int n)
{
    return (n & 1) == 0;
}
编辑于 2015-01-29 14:48:14 回复(0)
phoenix6418头像 phoenix6418
也可以两个pointer同时从左边走

19   public static void oddAndEven (int [] nums) {
20       if (nums != null && nums.length != 0) {
21          for (int odd = 0, even = 0; even < nums.length; even ++) {
22             if (nums [even] % 2 != 0) {
23                int temp = nums [even];
24                nums [even] = nums [odd];
25                nums [odd] = temp;
26                odd ++;
27             }
28          }
29       }
30    }

发表于 2017-09-26 09:58:40 回复(0)
yellow0523头像 yellow0523
    设置两个指针，odd指针指向头部·，向后移动，even指针指向尾部，向前移动，odd遇到偶数停止，even遇到奇数停止，两者数据进行交换，当odd指针不在even指针之前时，停止操作，对数组划分的操作完成。

import java.util.Scanner;

public class PartitionOddAndEven {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("请输入数组元素:");
        int a[] = new int[99];
        int temp;
        for (int i = 0; i < 9; i++) {
            a[i] = sc.nextInt();
        }
        for(int odd=0,even=8;odd<even;odd++,even--){  //设置两个指针，odd指向头，even指向尾部
            while(a[odd]%2==1 && odd<even){
                odd++;
            }//odd停止的地方为偶数
            while(a[even]%2==0 && odd<even){
                even--;
            }//even停止的地方为奇数
            temp=a[odd];
            a[odd]=a[even];
            a[even]=temp;//交换完成之后指针马上继续移动，odd右移，even左移
        }
        System.out.print("排序后的数组元素为:");
        for (int i = 0; i < 9; i++) {
            System.out.print(a[i]+" ");
        }
    }
}
发表于 2020-03-14 00:13:14 回复(0)
小夏头像 小夏
难道不是至少遍历一次？最少O（N）
发表于 2017-04-28 11:29:37 回复(1)
码仔头像 码仔 
int SwapArray(int *a, int len)
{
	int low, high;
	int t;
	
	low = 0;
	high = len - 1;
	
	while (1) {
		while (a[low] % 2 == 1 && low < high) low++;
		while (a[high] % 2 == 0 && low < high) high--;
		if (low == high) break;
		t = a[low];
		a[low] = a[high];
		a[high] = t;
	}

	return 0;
}

发表于 2015-09-10 17:45:28 回复(0)
等待复活头像 等待复活 
#include<iostream>
using namespace std;
int main()
{ 
    int n[8]={1,2,3,4,5,6,7,8};
    int t;
    for(int i=0;i<8;i++)
    {
       if((n[i]&1)==1)
       {
          for(int j=i;j>0;j--)
          {
              t=n[j];
              n[j]=n[j-1];
              n[j-1]=t;
          }
       }
    }
    for(int a=0;a<8;a++)
    {
        cout<<n[a]<<endl;
    }
    return 0;
}

编辑于 2015-05-20 09:47:57 回复(0)
REDStone头像 REDStone
从左右两边同时开始进行，首先左边先开始，如果是奇数就继续向下走，如果是偶数的话就放到临时空间tmp，然后从右边开始进行过程类似与左边遇到奇数时把它放到左边的那个里面，然后把tmp的值放到右边的这里，然后左边从下一个继续进行，过程类似于前边，最后当左边的下标大于等于右边下标时就停止时间复杂度为n
发表于 2014-11-22 23:15:43 回复(2)
牛客-007头像 牛客-007
类似快排的思想，用两个指针，一个指向左边的偶数，一个指向右边的奇数，然后交换两个数，移动两个指针，继续上面操作
发表于 2015-01-10 13:16:18 回复(0)
TREEEEEEEESES头像 TREEEEEEEESES
双指针法，偏竞***代码
两个指针从头开始遍历
每次寻找未遍历部分的第一个奇数arr[r]
与未遍历部分开头交换
确保前l个数都为奇
时间复杂度 O(N)
空间复杂度 O(1) 
#include <iostream>

void devide(int arr[], int len){
	int l, r;
	for(l = 0, r = 0; r <= len && l <= len; l++){
		while(r <= len && (arr[r]%2 == 0))	r++;	//寻找后方第一个奇数 
		if(r <= len)	std::swap(arr[l], arr[r]); 	//与此处偶数交换，确保已遍历过的左方全部为奇 
	}
}


编辑于 2025-09-14 21:41:28 回复(0)
王奕_头像 王奕_

num=[int(x) for x in input("Enter numbers separated by space: ").split()]

i=0

j=len(num)-1

while i<j:

    if(num[i]%2==0):

        i+=1

    else:

        if(num[j]%2!=0):

            j-=1

        else:

            num[i],num[j]=num[j],num[i]

            i+=1

            j-=1

print(num)

发表于 2025-09-02 17:31:33 回复(0)
buzzx头像 buzzx

双指针

public class frag{
    public void frag(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            while (left < right && (nums[left] & 1) == 1) left++;
            while (left < right && (nums[right] & 1) == 0) right--;
            if (left < right) {
                int tmp = nums[left];
                nums[left] = nums[right];
                nums[right] = tmp;
                left++;
                right--;
            }
        }
    }
}
发表于 2022-04-13 22:03:00 回复(0)
杨慧清头像 杨慧清 
#两个指针，一个从头开始，一个从尾开始，头指针遇到偶数则停下来，尾指针遇到奇数停下来，互相交换
arr=list(map(int,input().split()))
low = 0
high = len(arr) - 1
while True:
    while arr[low] % 2 != 0 and low < high:
        low += 1
    while arr[high] % 2 != 1 and low < high:
        high -= 1
    if low == high:
        break
    arr[low], arr[high] = arr[high], arr[low]

for i in arr:
    int(i)
    print (i,end=' ')
发表于 2020-09-03 09:41:51 回复(0)
nxncnznd头像 nxncnznd
int _tmain(int argc, _TCHAR* argv[])
{
    int a[10] = { 2, 5, 16, 7, 3, 10, 45, 32, 33, 71 };
    for (int i = 0; i < 10;i++)
    {
        if (a[i]%2==0)
        {
            for (int j = 9; j > i;j--)
            {
                if (a[j]%2==1)
                {
                    int temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                    break;
                }
            }
        }
    }

    for (int t = 0; t < 10;t++)
    {
        printf("%d ",a[t]);
    }

    getchar();
}
发表于 2018-03-01 03:18:14 回复(0)
ahuangliang头像 ahuangliang 

	intSwapArray(int*a, intlen)





	{





	    int*first = a, *last = a + len - 1;





	     





	    while(first < last) {





	        while((*first & 1) && first < last) ++first;





	        while(!(*last & 1) && first < last) --last;





	        int t = *first; *first++ = *last; *last-- = t;





	    }





	 





	    return0;





	}

发表于 2016-08-05 19:25:58 回复(0)
夏雨天头像 夏雨天
#include<iostream>
#include <vector>
#include <iterator>

using namespace std;

int main()
{
vector<int >num;
int n = 0;
cin >> n;

int i = 0, j = n - 1;

int temp = 0;

for (i = 0; i < n;i++)
{
cin >> temp;
num.push_back(temp);
}

i = 0;

while (true)
{
while (1 == num[i] % 2)
{
i++;
}

while (0 == num[j] % 2)
{
j--;
}

//交换
num[i] = num[i] + num[j];
num[j] = num[i] - num[j];
num[i] = num[i] - num[j];
i++;
j--;

if (i>j)
{
break;
}
}

copy(num.begin(), num.end(), ostream_iterator<int>(cout, " "));
return 0;
}
发表于 2016-01-13 16:37:51 回复(0)
软贱攻城狮头像 软贱攻城狮
<div> var likeQuickSort = function(oArr){ </div> <div> <span> </span>var left = 0 ,right = oArr.length; </div> <div> <span> </span>while(left&lt;right){ </div> <div> <span> </span>while (oArr[left]%2!=0) { </div> <div> <span> </span>//是奇数 </div> <div> <span> </span>left++; </div> <div> <span> </span>}; </div> <div> <span> </span>while (oArr[right]%2!=1) { </div> <div> <span> </span>right --; </div> <div> <span> </span>}; </div> <div> <span> </span>if (left&lt;right) { </div> <div> <span> </span>var tmp = oArr[left]; </div> <div> <span> </span>oArr[left] = oArr[right]; </div> <div> <span> </span>oArr[right]=tmp; </div> <div> <span> </span>}; </div> <div> <span> </span>} </div> <div> <span> </span>return oArr; </div> <pre class="prettyprint lang-js"> }</pre> <br />
发表于 2015-09-11 21:15:51 回复(0)
龙宫头像 龙宫 
#include <iostream>

using namespace std;

bool sort_arr(int *a,int len)
{
	if(a==NULL || len <1) return false;

	int tmp=a[0];
	int left=0;
	int right=len-1;

	while(left<right)
	{
		while(left<right && a[right]&1 != 0) right--;
		if(left<right) a[left++]=a[right];

		while(left<right && a[left]&1 == 1) left++;
		if(left<right) a[right--]=a[left];
	}

	a[left]=tmp;

	return true;
}

void print_arr(const int *p,int len)
{
	if(p==NULL || len <1) return;

	for(int i=0;i<len;i++)
	{
		cout<<p[i]<<" ";
	}
	cout<<endl;
}
int main()
{
	int arr[]={1,2,3,4,5,6,7,8,9,10};
	int len=sizeof(arr)/sizeof(arr[0]);

	print_arr(arr,len);
	sort_arr(arr,len);
	print_arr(arr,len);

	return 0;
}

发表于 2015-09-11 17:34:04 回复(0)
callmehan头像 callmehan
<pre class="prettyprint lang-java">public static void dealWithArray(int[] arr){ &nbsp;&nbsp;int i = 0; int j = arr.length-1; while(i &lt; j){ while(arr[i]%2==1 &amp;&amp; i&lt;j) i++; &nbsp; while(arr[j]%2==0 &amp;&amp; i&lt;j) j--; if(i &lt; j) swap(arr,i,j); } } public static void swap(int[] arr, i ,j){ if(i == j) return; arr[i] = arr[i] + arr[j]; arr[j] = arr[i] - arr[j]; arr[i] = arr[i] - arr[j]; }</pre> <br />
发表于 2015-09-11 14:58:40 回复(0)
时态的空白&amp;trade;头像 时态的空白&amp;trade; 
void changeArr(int *b, int size)
{
	int i=0, j=size-1;
	while(i<j)
	{
		if(b[i]%2!=0)
		{
			i++;
		}
		if(b[j]%2==0)
		{
			j--;
		}
		if(i<j)
		{
			if(b[i]%2==0 && b[j]%2!=0)
			{
				b[i] = b[i] +b[j];
				b[j] = b[i] - b[j];
				b[i] = b[i] - b[j];
			}
		}
	}
}

发表于 2015-09-08 20:13:19 回复(0)
coco酱是个程序媛哟头像 coco酱是个程序媛哟 
class Solution():
    def divide(self, nums):
        start = 0
        end = len(nums) - 1
        while start < end:
            while start < end and nums[start] % 2 == 1:
                start += 1
            while end > start and nums[end] % 2 == 0:
                end -= 1
            temp = nums[end]
            nums[end] = nums[start]
            nums[start] = temp
        return nums

编辑于 2015-09-07 20:50:25 回复(0)
YvY头像 YvY
java代码 
public static void px(int[] nub){
		int j=nub.length-1;//用于记录偶数的最左位
		int temp = 0;
		f: for(int i = 0 ; i < nub.length ; i ++){
			if((nub[i]&1)==0){//如果nub[i]是偶数
				while((nub[j]&1)==0){//当要交换的数是偶数时候
					if(i==j){
						break f;
					}
					j--;
				}
				temp = nub[j];
				nub[j]=nub[i];
				nub[i]=temp;
				j--;
			}
			if(i==j){
				break;
			}
		}
		for(int i = 0 ;i<nub.length ; i++){
			System.out.println("nub["+i+"]="+nub[i]);
		}
	}

发表于 2015-08-18 17:08:35 回复(0)
提交观点

问题信息

C++工程师 编程基础 C++ Java 百度 2011 Java工程师
来自：百度2011研发工程师笔试卷
难度：
24条回答 18735浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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