面接問題14:奇数が偶数より前になるように配列順を調整する

タイトル説明:Online judge
整数配列を入力し、すべての奇数が配列の前半に位置し、すべての偶数が配列の後半に位置し、奇数と奇数、偶数と偶数の間の相対位置が変わらないことを保証する関数を実現します.
入力:
各入力ファイルには、テストケースのセットが含まれています.各テストケースについて、最初の行にnを入力し、その配列の数を表します.次の行にはn個の整数を入力します.配列内のn個の数を表します.
出力:
各テストケースに対応して、調整された配列を表すn個の行を入力します.数字と数字の間にはスペースがあり、最後の数字の後ろにはスペースがありません.
サンプル入力:

5
1 2 3 4 5

サンプル出力:

1 3 5 2 4

問題解決の考え方:
問題を解く構想の1:時間の複雑さを考慮しないで、最初からこの配列をスキャンして、偶数に出会うたびに、この数字を出して、そしてこの数字の後ろのすべての数字を前に1位移動します.ずらすと配列の末尾に空席があり、偶数をこの位置に入れます.このような方法は時間的複雑度がO(n^2)であり,効率的には満足できない.次に,解題構想2の改良アルゴリズムについて説明する.
解題構想2:私たちは2つのポインタを採用して配列を維持し、最初のポインタは初期化時に配列の最初の位置を指し、それは後移動を指す.2番目のポインタは配列の末尾を指し、前方にのみ移動します.2つのポインタが出会う前に、最初のポインタは常に2番目のポインタの前にあります.最初のポインタが偶数を指し、2番目のポインタが奇数を指している場合は、この2つの数字を交換します.このようにして、1番目のポインタと2番目のポインタが重なるまで行います.
JAvaコード:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;


public class Problem_14 {
	
	public static void main(String[] args) throws IOException {
		BufferedReader bu = new BufferedReader(new InputStreamReader(System.in));
		StreamTokenizer str = new StreamTokenizer(bu);
		while( str.nextToken() != StreamTokenizer.TT_EOF){
			int num = (int)str.nval;
			if (num < 1){
				continue;
			}
			int [] array = new int[num];
			for( int i = 0; i < num; i++ ){
				str.nextToken();
				array[i] = (int)str.nval;
			}//end for
			
			int p = 0; 
			int q = num-1;
			while( p < q){
				while(array[p]%2 == 1){
					p++;
				}//end while
				
				while(array[q]%2 ==0 ){
					q--;
				}//end while
				if(p < q){
					int temp = array[q];
					array[q] = array[p];
					array[p] = temp;
					p++;
					q--;
				}//end if
			}//end while
			
			for( int i = 0; i < num; i++ ){
				if (i < num -1){
					System.out.print(array[i]+" ");
				}else{
					System.out.println(array[i]+"
");		
				}				
			}
				
		}//end while
	}	
}

C++コード:

int  *exch(int arr[], int n)
{
  int left = 0, right = n - 1;
  int *p = (int *)malloc(sizeof(int) * n);
  if(p == NULL)
    return NULL;
 
  for(int i = 0, j = n - 1; n > 0; )
  {
    if(arr[i] % 2 == 1)
    {
      p[left++] = arr[i];
      n--;
    }
    i++;
    if(arr[j] % 2 == 0)
    {
      p[right--] = arr[j];
      n--;
    }
    j--;
  }
   
  return p;
}
int main(int argc, char **argv)
{
  int n, i = 0;
  int *pp = (int *)malloc(sizeof(int) * 1000000);
  scanf("%d", &n);
  while(n > 0 && scanf("%d", pp + i)!=EOF)
  {
    n--;
    i++;
  }
  int *p = exch(pp, i);
   
  for(int j = 0; j < i - 1; j++)
    printf("%d ", p[j]);
  printf("%d", p[i - 1]);
 
  return 0;
}

Cコード:

#include <stdio.h>
#include <stdlib.h>
 
int main(){
    int N,i,j,k,t,arr[100000];
    //bool first;
    int first;
    //cin>>N;
    while(scanf("%d",&N)!=EOF)
    {
        first=1;
        k=0;
        for(i=0;i<N;i++)
        {
            //cin>>t;
            scanf("%d",&t);
            if(t & 1)
            {
                if(first)
                {
                    //cout<<t<<" ";     
                    printf("%d",t);
                    first=0;
                }
                else
                    //cout<<t<<" ";
                    printf(" %d",t);
            }                   
            else           
                arr[k++]=t;                         
        }
        for(j=0;j<k;j++)         
            //cout<<arr[j]<<" ";    
            printf(" %d",arr[j]);
    }
    return 0;
}

テスト例:
機能テスト:入力配列の奇数、偶数が交互に現れ、入力配列のすべての数字が偶数または奇数である.
特殊入力テスト:空のポインタを入力し、入力配列には1つの数値しか含まれません.