algorithm - 奇数元素在奇数位置，偶数元素在偶数位置

Question

这是在一次采访中提出的问题。请提出一些看法。给定一个包含所有正整数的数组。您必须以奇数元素位于奇数位置，偶数元素位于偶数位置的方式排列元素。

PS。没有多余的空间。O(N) 解决方案

Answer 1

遍历偶数位置，直到找到奇数。遍历奇数位置，直到找到偶数（使用不同的索引）。交换两个数字，然后重复。

Answer 2

您是否允许将数组的大小加倍？否则，这个问题没有意义。为什么？！？假设你得到一个充满奇数的数组，那么你能想到任何解决方案吗？不，那里没有。

因此，我假设您可以将数组的大小加倍。然后对于任何 i，将 i 元素 ( a(i) ) 放入位置 2*i 或 2*i +1 取决于 a(i) 是偶数还是奇数。

Answer 3

两个与给定数组大小相同的新数组 OddArray 和 EvenArray。遍历给定的数组并继续将所有奇数发送到 OddArray 并保持奇数位置和偶数到 EvenArray 保持数字在偶数位置。

效率为 O(n)，额外内存为 2n，其中 n 是原始数组的大小。

Answer 4

list1 = [5, 7, 6, 8, 10, 3, 4, 9, 2, 1, 12]
odd_list = []
even_list = []
for i in range(len(list1)):
    if((list1[i] % 2) == 0):
        even_list.append(list1[i])
    else:
        odd_list.append(list1[i])
print(list1)
j = 0
k = 0
for i in range(0, len(list1)):
    if((i % 2 == 0) and (j < len(odd_list))):
        list1[i] = odd_list[j]
        j += 1
    elif(k < len(even_list)):
        list1[i] = even_list[k]
        k += 1
print(list1)

Answer 5

//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;
    }
}