首页 > 试题广场 >

仅用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)
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)
zgljl2012头像 zgljl2012 
package Test;

public class Test3 {
	
	/**
	 * 算法：计数器为0，从第一个开始判断，若是奇数，就与计数器指定位置交换数据，计数器加1；若是偶数，则不作处理。
	 * @param v
	 */
	public void fun(int[] v) {
		for(int i = 0,j=0;i < v.length; i++) {
			if(v[i] % 2 != 0) { 
				swap(v, i, j);
				j++;
			}
		}
	}
	
	public void swap(int[] v, int i, int j) {
		int tmp = v[i];
		v[i] = v[j];
		v[j] = tmp;
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] v = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
		Test3 test = new Test3();
		test.fun(v);
		for(int i = 0; i < v.length; i++) {
			System.out.print(v[i]+" ");
		}
	}

}


编辑于 2015-08-10 12:49:41 回复(0)
大城市小葫芦头像 大城市小葫芦
#include <iostream>
#include <string>
#include <vector>
using namespace std;
void exchange(int *p,int *q){
    int temp=*p;
    *p=*q;
    *q=temp;
}

/*******方法1******/
void array_move(int array[],int length){
    if(array==NULL||length<=0)
        return ;
    int cnt_of_odds=0;
    for(int i=0;i<length;i++){
        if(array[i]%2!=0)
            cnt_of_odds++;              //首先计算出奇数出现的次数，然后推算出偶数最终应该放在数组的什么位置上
    }
    int cnt_of_evens=length-cnt_of_odds;
    int *pEven=array+cnt_of_odds;         //利用两个指针，pEven,pOdd，pEven指向的是偶数序列
    int *pOdd=array;
    int cnt_of_swap=cnt_of_evens;
    while(pEven!=array+length){            //  如果在偶数区域内发现奇数，则在奇数区域内找到第一个偶数与之交换，然后分别++奇数和偶数
        if(*pEven%2!=0){
            while(*pOdd%2!=0&&pOdd!=array+cnt_of_odds)
                pOdd++;                                     //指针
            exchange(pOdd,pEven);
            pOdd++;
            pEven++;
        }
        else{
            ++pEven;                          //如果在偶数区域内偶数指针指向的是偶数，则++偶数指针
        }
    }
}
int main(){
    int array[]={4,3,2,1,5,6,7};
    int length=sizeof(array)/sizeof(int);
    array_move(array,length);
    for(int i=0;i<length;i++)
        cout << " " << array[i];
    return 0;
}
发表于 2015-06-23 17:14:34 回复(0)
提交观点

问题信息

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

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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