将列表中的奇数和偶数移动到奇数和偶数位置

Question

我有一个列表，其中包含相等数量的奇数和偶数。目标是修改列表以在奇数索引处具有奇数整数，在偶数索引处具有偶数整数。

这是我的方法：

我找出偶数索引和奇数索引处的数字。然后找出偶数索引处的奇数和奇数索引处的偶数。最后交换错位的数字。

 x = [3, 2, 5, 6, 4, 7, 8, 9, 10, 11]
even_pos = []
odd_pos = []
for i in range(len(x)):
    if x[i] % 2 == 0:
        even_pos.append(i)
    else:
        odd_pos.append(i)

even_pos_with_odd = []
odd_pos_with_even = []

for j in range(len(even_pos)):
    if even_pos[j] % 2 != 0:
        even_pos_with_odd.append(j)
    if odd_pos[j] % 2 == 0:
        odd_pos_with_even.append(j)

for n in range(len(even_pos_with_odd)):
    temp =  x[odd_pos[odd_pos_with_even[n]]]
    x[odd_pos[odd_pos_with_even[n]]] = x[even_pos[even_pos_with_odd[n]]]
    x[even_pos[even_pos_with_odd[n]]] = temp

虽然它有效，但我对解决方案不是很满意。有没有更有效的解决方案来解决我的问题？我的目标是使 x[] 像 [2, 3, 6, 5, 4, 7, 8, 9, 10, 11] 可能以相同的奇偶格式排序。

原文由 juggernaut 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

创建列表的 _副本_（仅用于创建等长的新列表），然后使用两个计数器跟踪将偶数和奇数插入新列表的位置，每次将索引递增 2：

 def odd_even_sieve(x):
    output = x[:]
    even_index, odd_index = 0, 1
    for value in x:
        if value % 2 == 0:
            output[even_index] = value
            even_index += 2
        else:
            output[odd_index] = value
            odd_index += 2
    return output

这比尝试就地交换所有内容要简单得多。

演示：

 >>> def odd_even_sieve(x):
...     output = x[:]
...     even_index, odd_index = 0, 1
...     for value in x:
...         if value % 2 == 0:
...             output[even_index] = value
...             even_index += 2
...         else:
...             output[odd_index] = value
...             odd_index += 2
...     return output
...
>>> odd_even_sieve([3, 2, 5, 6, 4, 7, 8, 9, 10, 11])
[2, 3, 6, 5, 4, 7, 8, 9, 10, 11]
>>> odd_even_sieve([19, 11, 23, 16, 18, 20])
[16, 19, 18, 11, 20, 23]

对于已排序的输出（奇数和偶数独立排序），只需对输入进行排序：

 >>> odd_even_sieve(sorted([3, 2, 5, 6, 4, 7, 8, 9, 10, 11]))
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
>>> odd_even_sieve(sorted([19, 11, 23, 16, 18, 20]))
[16, 11, 18, 19, 20, 23]

原文由 Martijn Pieters 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

要将所有偶数项移动到偶数索引并将所有奇数项移动到奇数索引中 O(n**2) 时间：

 def fix_odd_even_indices(lst):
    for i in range(len(lst)):
        j = i
        while i & 1 != lst[i] & 1: # element is in the wrong place
            j += 1
            lst[i], lst[j] = lst[j], lst[i] # swap

如果奇数和偶数不相等，代码可能会引发 IndexError 。

例子：

 lst = [3, 2, 5, 6, 4, 7, 8, 9, 10, 11]
fix_odd_even_indices(lst)
print(lst)
# -> [2, 3, 6, 5, 4, 7, 8, 9, 10, 11]

---

这是一个返回副本的线性解决方案：

 def fixed_odd_even_indices(seq):
    L = [None]*len(seq)
    L[1::2] = [x for x in seq if x & 1] # odd
    L[::2] = [x for x in seq if not x & 1] # even
    return L

例子：

 print(fixed_odd_even_indices([3, 2, 5, 6, 4, 7, 8, 9, 10, 11]))
# -> [2, 3, 6, 5, 4, 7, 8, 9, 10, 11]

这是一个返回副本的线性单通道解决方案（它可能比以前的解决方案慢）：

 def fixed_odd_even_indices(iterable):
    odds, evens = [], []
    for x in iterable:
        (odds if x & 1 else evens).append(x)
    return [x for pair in zip(evens, odds) for x in pair]

例子：

 L = fixed_odd_even_indices(map(int, sys.stdin)) # input one integer per line

原文由 jfs 发布，翻译遵循 CC BY-SA 3.0 许可协议