在面试中有这样一个问题,给定一个包含所有正整数的数组,你需要以这样一种方式排列元素:奇数元素在奇数位置,偶数元素在偶数位置。请提供一些看法。
附注:不使用额外的空间,O(N)解决方案。
附注:不使用额外的空间,O(N)解决方案。
迭代偶数索引位置,直到找到一个奇数。使用不同的索引迭代奇数位置,直到找到一个偶数。交换这两个数字,然后重复上述过程。
你可以将数组的大小加倍吗?否则,这个问题就没有意义。为什么?假设你得到一个由奇数填充的数组,你能想到任何解决方案吗?不能。
因此,我假设你可以将数组的大小加倍。然后对于任何i,根据a(i)是偶数还是奇数,将i元素(a(i))放入位置2 * i或2 * i +1。
//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;
}
}
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)
O(n)
时间和原地执行中并不难。如果超过一半(+1)是偶数(或超过一半(+1)是奇数),则会出现问题。 - A. Webb