algorithm - 奇数の位置に奇数要素、偶数の位置に偶数要素

Question

これはあるインタビューで尋ねられた質問です。いくつかのビューを提案してください。すべて正の整数を含む配列が与えられます。奇数要素が奇数の位置に、偶数要素が偶数の位置になるように要素を配置する必要があります。

PS。余分なスペースはありません。O(N) ソリューション

Answer 1

奇数が見つかるまで、偶数の位置を繰り返します。(別のインデックスを使用して)偶数が見つかるまで、奇数の位置を反復します。2 つの数字を入れ替えて、繰り返します。

Answer 2

配列のサイズを 2 倍にすることはできますか? そうでなければ、質問は意味を成しません。どうして？！？奇数でいっぱいの配列が与えられたと仮定すると、解決策を思いつくことができますか? いいえ、ありません。

したがって、配列のサイズを 2 倍にすることが許可されていると仮定します。次に、任意の i について、a(i) が偶数か奇数かによって、i 要素 ( a(i) ) を位置 2*i または 2*i +1 に配置します。

Answer 3

指定された配列と同じサイズの 2 つの新しい配列 OddArray と EvenArray。指定された配列をトラバースし、すべての奇数を OddArray に送信し続け、奇数の位置に保持し、偶数を偶数の位置に保持して EvenArray に送信します。

効率は O(n) になり、余分なメモリは 2n になります。ここで、n は元の配列のサイズです。

Answer 4

//Putting even number on even position and odd number on odd position
package com.learnJava;

public class ArrangeArray {

    private int [] array={2,5,7,8,1,6,9};
    private int len=array.length;
    public static void main(String [] args)
    {
        ArrangeArray a=new ArrangeArray();
        a.print();
        a.arrange();
        a.print();

    }
    public  void print()
    {
        for(int i=0;i<array.length;i++)
        {
            System.out.print(array[i] + " ");

        }
        System.out.println();
    }
    public void arrange()
    {
        int oddinx=1;
        int evenidx=0;
        while(true)
        {
            while(evenidx<len && array[evenidx]%2==0)
            {
                evenidx+=2;
            }
            while(oddinx<len && array[oddinx]%2==1)
            {
                oddinx+=2;
            }
            if (evenidx < len && oddinx < len)
                swap (evenidx, oddinx);
            else
                break;

        }

    }
    public void swap(int a,int b)
    {
        int tmp=array[b];
        array[b]=array[a];
        array[a]=tmp;
    }
}