奇数位置的元素为奇数，偶数位置的元素为偶数

Question

在面试中有这样一个问题，给定一个包含所有正整数的数组，你需要以这样一种方式排列元素：奇数元素在奇数位置，偶数元素在偶数位置。请提供一些看法。

附注：不使用额外的空间，O(N)解决方案。

- username_4567

---

你有尝试过解决它吗？ - Blender

给定一个包含所有正整数的数组。那是一个很大的数组！ - A. Webb

我喜欢那些与实际业务需求毫无关系的面试问题。我想给面试官投反对票。说真的，他们应该问一些像“你如何防止SQL注入？”、“你能向我描述XSRF和XSS吗？”、“你如何处理一个业务需求需要更改的情况，因为你发现这会引起业务没有预料到的问题？”这样的问题。 - David

我尝试解决问题，但无法得到O(n)的解决方案。我的方法是对元素进行排序，然后进行重新排列，但结果证明这不是一个好的解决方案。 - username_4567

@DavidStratton：在面试中无法解决现实生活中的问题。我其实很喜欢这个问题——它不太难，而且你可以看到候选人如何处理问题。 - Sven Marnach

实际上，如果有解决方案，则此问题在O(n)时间和原地执行中并不难。如果超过一半（+1）是偶数（或超过一半（+1）是奇数），则会出现问题。 - A. Webb

Answer 1

迭代偶数索引位置，直到找到一个奇数。使用不同的索引迭代奇数位置，直到找到一个偶数。交换这两个数字，然后重复上述过程。

- Sven Marnach

Answer 2

你可以将数组的大小加倍吗？否则，这个问题就没有意义。为什么？假设你得到一个由奇数填充的数组，你能想到任何解决方案吗？不能。

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

- nmoses

---

从高索引开始。 - greybeard

Answer 3

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

- Anil Jain

---

（将您的代码缩进四个或更多空格。不要编写未注释的代码。）不鼓励仅包含代码的答案。这个答案与Sven Marnach's有何不同？如果偶数和奇数值的数量不相等会发生什么？（此问题不使用“语言标签”：您使用的是哪种语言编码？） - greybeard

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)

- Manjunath Sharma

Answer 5

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

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

- Romaan

---

抱歉，忘记提醒不要有额外的空格了！！ - username_4567

在大小为n的数组中，您能否确认恰好有n/2个奇数和n/2个偶数？ - Romaan