时间戳

首页 > 解决方案 > 先排列奇数，再排列偶数。奇偶顺序不应该改变

arrays - 先排列奇数，再排列偶数。奇偶顺序不应该改变

问题描述

下面是在不改变原始数组中偶数/奇数顺序的情况下重新排序奇数后跟偶数的代码片段。

输入 - {1, 4, 8, 3, 9, 12, 7} 输出 - {1, 3, 9, 7, 4, 8, 12}

我们可以从空间中的 O(n2) 改进这一点（不使用额外空间）吗？

public  static void reOrder(int[] arr) {
     int evenIndex  = arr.length;
     for(int i=0; i < arr.length;i++) {
            if(arr[i] % 2 == 0 && evenIndex == arr.length) //even index
                evenIndex = i;

            else if( arr[i] % 2 != 0 ) {
                if(i > evenIndex ) {
                    shift (arr, evenIndex , i);
                    evenIndex ++;
                }
            }
     }
}

static void shift(int[] arr, int evenIndex, int endIndex) {
    int temp = arr[endIndex];
    for(int i = endIndex; i > evenIndex ;i --) {
        arr[i] = arr[i-1];
    }
    arr[evenIndex] = temp;
}

标签： arraysalgorithmperformancebig-o

解决方案

您没有指定任何语言标签，所以我将使用 python 来回答（只是因为我现在使用它更快）。

如果您只关心空间复杂性，您可以执行以下操作：

l = [1, 4, 8, 3, 9, 12, 7]
even_index = -1

for index in range(0, len(l)):
    if (l[index] % 2) == 0:
        if even_index == -1:
            even_index = index
    else:
        if (index > 0) and (even_index > -1):
            num = l[index]
            l.insert(even_index, num)
            del l[index + 1]
            even_index += 1
print(l)

您保留第一个偶数所在位置的索引，并在发现奇数通过列表时插入它们。然后删除“旧”索引处的奇数（现在增加 1）。

我认为空间复杂度是你需要的，但是时间复杂度可以提高。

例如，在 Python 中 acollections.deque在这种情况下可能更好，但时间复杂度不是优先考虑的问题。

推荐阅读