首页 > 试题广场 >

仅用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)
也可以两个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)
    设置两个指针,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)
从左右两边同时开始进行,首先左边先开始,如果是奇数就继续向下走,如果是偶数的话就放到临时空间tmp,然后从右边开始进行过程类似与左边遇到奇数时把它放到左边的那个里面,然后把tmp的值放到右边的这里,然后左边从下一个继续进行,过程类似于前边,最后当左边的下标大于等于右边下标时就停止时间复杂度为n
发表于 2014-11-22 23:15:43 回复(2)
类似快排的思想,用两个指针,一个指向左边的偶数,一个指向右边的奇数,然后交换两个数,移动两个指针,继续上面操作
发表于 2015-01-10 13:16:18 回复(0)

双指针

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)
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)
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)
<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)
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)
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)
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)