python - 给定一个2n长的数组将奇数放在偶数前面

Question

给定一个2n长数组，其中n个奇数和n个偶数，对数组进行排序将奇数放在前半部分，偶数放在后半部分。要求：

1. 不改变原来的奇偶各自的相对顺序

2. 只申请常数的空间

3. 时间复杂度为O(n)

举例：给出1 2 3 4 5 6
排序后为 1 3 5 2 4 6

PS：请一定仔细阅读3个条件，去掉其中任意一个都变得简单，并且网上我搜到的答案都是缺少其中某个条件的。因此我怀疑这题是否有解。

---

看了大家的回答，基本可以分为2种情况：

1. 用链表可以轻易解决这道题，当然如果把数组转成链表因为需要申请2n长度的next数组，所以认为还是申请额外空间了

2. 只管输出，如果只要求输出结果那遍历2遍就行了，但这样题目变得太过简单

因为这是一道面试题，我想可以从上面2方面和面试官沟通，我只是凭记忆写下这题，其中也许有自己的一些思维定势（比如没有强调一定是数组，或者没有强调必须要求数组排序只要求输出）。看了大家的讨论还是很有启发的。

---

找到了国外的链接，看了一圈讨论大部分认为没有O(n)时间O(1)空间的解法
https://www.careercup.com/question?id=5201559730257920

---

另外说下我自己对这题的一个思考，可以观察到，假如一个数组是符合最终条件的，那么发现当且仅当只交换相邻的两个奇偶数是不会破坏相对顺序的，那么只需给出一个策略找出从最终状态转到题目起始状态的就行了。
另外，不要纠结于奇偶分别的大小问题，比如4 5 3 1 2 6和2 1 3 5 4 6是等价的，只是一个简单的替换，只要将奇数按1 3 5……这样的顺序，偶数按2 4 6……这样的顺序排好就行了。

Answer 1

Under your three conditions, arrays are not possible, but linked lists are.

Answer 2

It’s very easy to use a linked list. Just change the pointer. It’s done in one traversal. If you encounter an even number, insert it into the end of the queue (only change the pointer without applying for memory). Ignore the odd number. But if you want to sort the odd and even numbers separately, it’s basically There is no O(n) algorithm

L = [1, 2, 3, 4, 5, 6]
index = 0
for _ in range(len(L)):
    if L[index] % 2 == 1:
        index += 1
    else:
        L.append(L.pop(index))
print(L)

#include <iostream>
#include <list> 

using namespace std;

int main() {
    list<int> L;
    int n = 3; 
    // 初始化链表
    for(int i = 1; i <= n * 2; i++)
        L.push_back(i);
    // 划分奇偶数
    for(list<int>::iterator it = L.begin(); 0 < n; ++it){
        if(*it % 2 == 0){  // 如果是偶数
            L.push_back(*it); // 插入尾节点 O(1)
            L.erase(it); // 删除节点 O(1)
            n -= 1;
        }      
    }
    // 打印链表
    for(list<int>::iterator it = L.begin(); it != L.end(); ++it)
        cout << *it << ' ';
    cout << endl;
        
    return 0;
}

Many people have said that it is easy to implement using linked lists, but not with arrays (to maintain stability, time O(n), space O(1)). If anyone can, show your code and let us worship you. .

At first glance, there seems to be a solution to the unsolvable problem. Let me sort it out.

def Foo(L):
    # L = [0, 2, 4, 1, 3, 5]
    length = len(L)
    sk = max(*L, length) + 1# secret key
    # 32位的话最多是支持4万多的数据量，且最大值也不超过46340
    assert sk < 46340, 'sk must be less than 46340' 
    li = 0                  # left index
    ri = length - 1         # right index
    uli = li                # unsorted left index
    uri = ri                # unsorted right index
    lli = length // 2 - 1   # left last index
    rfi = lli + 1           # right first index
    # 第一个循环先区别就位和未能就位的元素，同时将index信息加密到未能就位的元素数据中
    # 这里用的加密文法是number = -(num + sk * indnx),将其变成一个负值
    # 解密可以用index, num = pmod(abs(number), sk)来解密
    while li <= ri:
        # 左边扫描到奇数
        if L[li] % 2 == 1:
            L[li], L[uli] = L[uli], L[li]
            li += 1
            uli += 1
        # 右边扫描到偶数
        elif L[ri] % 2 == 0:
            L[ri], L[uri] = L[uri], L[ri]
            ri -= 1
            uri -= 1
        # 当左为偶，且右为奇
        else:
            L[li], L[ri] = L[ri], L[li]
            L[li] = -(L[li] + sk * lli) # 加密乱序的元素
            lli -= 1
            L[ri] = -(L[ri] + sk * rfi) # 加密乱序的元素
            rfi += 1
            li += 1
            ri -= 1
    print(L) # 加密后 [-39, -20, -1, -89, -70, -51]
    # 解密
    for i in range(uli, uri):
        if L[i] < 0:
            index, number = pmod(abs(L[i]), sk)
            next_num = L[index]
            while next_num < 0:                
                L[index] = number
                index, number = pmod(abs(next_num), sk)
                next_num = L[index]
    print(L) # 解密 [1, 3, 5, 0, 2, 4]
    return L

It is best not to use numbers larger than length to test. If the data is not large, it should be fine, otherwise you will have to consider overflow issues.

Answer 3

I want to do it this way, I don’t know what you think:

Just start from the head of the array, and don’t move when you encounter an odd number. If you encounter an even number, put it at the end of the array, until n even numbers have been moved.

1. 奇數偶數各自順序不變
2. 只需要一個整數記目前搬動幾個了
3. 就最差 2n 步(偶數都在後面的情況)

---

P.S. Why give negative points? If you think there is anything wrong with the answer, you can comment and discuss it first before giving negative points to others. I don’t think it is necessary to step on the people who are discussing seriously here and are full of doubts about negative points. ..

Answer 4

I think it’s impossible. In the final analysis, this is a ranking problem.
We assume that quick sort is used (of course it does not meet the stability problem, I am just saying casually, if you want stability, you can use a binary tree to sort), then just set the comparison condition to odd numbers being larger than even numbers.
But obviously the sorting problem can only be O(n) in some special cases.
So I think it’s impossible.

Answer 5

Looking at it as a general sorting problem, it seems impossible, but this question has three very demanding conditions.
There are also some favorable conditions that can be taken advantage of. The two important points are:

1. There are as many odd numbers as even numbers, and the length of all arrays is n + n

2. Odd and even numbers keep their original order, no need to sort by size

I use golang to implement the following:

package main

import "fmt"

func main() {
    var n = 4
    // var intArr = []int{12, 2, 4, 6, 5, 1, 7, 3}
    // var intArr = []int{1, 2, 3, 4, 5, 6, 7, 8}
    var intArr = []int{1, 2, 4, 6, 8, 3, 5, 7}
    var odd = 0
    var even = 2*n - 1

    for i := 0; i < len(intArr); i++ {
        if i > even {
            break
        }

        // fmt.Printf("before: %v\n", intArr)
        if intArr[i]%2 == 0 { // even number
            intArr[even], intArr[i] = intArr[i], intArr[even]
            even--
        } else { // odd number
            intArr[odd], intArr[i] = intArr[i], intArr[odd]
            odd++
        }
        // fmt.Printf("after : %v\n", intArr)
    }

    // print result
    for i := 0; i < odd; i++ {
        fmt.Println(intArr[i])
    }
    for i := even; i > odd-1; i-- {
        if intArr[i]%2 != 0 {
            fmt.Println(intArr[i])
        }
    }
    for i := 2*n - 1; i > even; i-- {
        fmt.Println(intArr[i])
    }
    for i := odd; i < even+1; i++ {
        if intArr[i]%2 == 0 {
            fmt.Println(intArr[i])
        }
    }
}

Answer 6

The requirements of the original question are translated
1) The time complexity is linear
2) The space complexity is O(k)
3) Stable
If the time complexity is O(n), it means that comparison sorting is no longer possible. The best average time complexity of comparison sorting is O(nlgn), such as quick sorting, etc.
This is already a mathematically proven conclusion of "Introduction to Algorithms".
The only ones with linear time are counting, buckets and radix, see https://www.byvoid.com/blog/sort-radix
That is, sorting is only
1) Counting - time complexity O(n) space complexity O( k+n)

http://www.geeksforgeeks.org/counting-sort/

2) Bucket sort - O(n) space complexity O(k+n)
http://www.growingwiththeweb.com/2015/06/bucket-sort.html

3) Radix sort O(n) and O(n+k)

So I personally think this question has no solution.
BTW: I suggest you take a good look at the link below
http://bigochheatsheet.com/

I have graduated from school a long time ago, so I don’t remember these conclusive things very clearly, which means that I am not responsible for the above conclusive things:-)
The poster can provide further evidence based on the above article.

But I am sure that the average time complexity based on comparison does not exceed O(nlogn), so it is recommended to look among the three of radix, bucket sort, and radix to see which one is closer to your requirements.

Answer 7

Here is an answer to a similar question:

https://www.quora.com/Given-an-array-of-integers-how-do-I-re-arrange-the-numbers-such-that-odd-numbers-occupy-odd-position-and -even-numbers-occupy-even-position

The solution to your problem is the same as it, because there is only one difference in the requirements: odd numbers are at odd index positions, and even numbers are at even index positions. The first answer in the link is the closest answer to what you want. The reason why it is only close is that it requires that the original array can accommodate a small amount of additional data.

Actually, I still doubt that there may be implicit conditions that the interviewer has not explained clearly to you when asking you questions. For example, if the 2n array itself is an ordered array, the situation will be very different.

Answer 8

I looked at the question and thought about it briefly. The ideas are as follows:

If it is the given array, there is no way to keep the relative order unchanged. The following code can only satisfy conditions 2 and 3:

for (i=0, j= 2n-1; i<n, j>n; ){
    if((n[i] % 2 == 1) && (n[j] % 2==0)){
        i++;
        j--;
    }
    
    if((n[i] % 2 == 0) && (n[j] % 2)==1){
           swap(n[i],n[j]);
           i++;
           j--;
    }
    
    if((n[i] %2 == 0) && (n[j] %2 == 0)){
        j--;
    }
    
    if((n[i] %2 == 1) && (n[j] %2 == 1)){
        i++;
    }
}

Just check from the beginning and the end, and judge each of the four situations.

If a linked list is given, the above three conditions are easily satisfied.

Another: I was stepped on for no reason. . .

Answer 9

https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.06.md

See the explanation for drawing inferences from one example.

The paper link is as follows

《STABLE MINIMUM SPACE PARTITIONING IN LINEAR TIME》

Answer 10

It feels like there is no solution.

Even this article makes an assumption that comparing the f-value of two numbers is constant time. It can be understood that each number has its own position information.
http://www.diku.dk/~jyrki/Paper/KP1992bJ.pdf

The following is my own analysis of No Solution:

This sequence is a permutation group. We know that from a sequence of length n to another sequence through pairwise permutation of numbers, up to n-1 permutation operations are required. The premise is that we know what each number needs to be permuted into. Location. However, since there is no way to know the position where each number is to be replaced (there is no place to store it), there is no obvious way to find the replacement position of each number in constant time (actually, I prefer that there is no such thing) method). So this shouldn't be possible.

Extra space can be used for auxiliary arrays.
If you have extra time, you can use a method similar to merge sort, non-recursive implementation, because it only divides odd and even, and can be exchanged in place.