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

세 가지 조건에서 배열은 작동할 수 없지만 연결된 목록은 작동할 수 있습니다.

Answer 2

연결된 목록을 사용하는 것은 매우 쉽습니다. 포인터를 한 번만 변경하면 짝수를 발견하면 대기열 끝에 삽입합니다(포인터만 변경하고 메모리를 적용하지 않음). . 홀수는 무시하세요. 그러나 여전히 홀수와 짝수를 구분해야 하는 경우에는 기본적으로 정렬을 위한 O(n) 알고리즘이 없습니다. 으아아아 으아아아

많은 사람들이 연결 목록을 사용하면 구현하기 쉽다고 말했지만 배열(안정성 유지, 시간 O(n), 공간 O(1))을 사용하면 구현하기가 쉽지 않다고 합니다. 가능하다면 코드를 보여주시면 감사하겠습니다. .

얼핏 보면 풀리지 않을 것 같은 문제에 대한 해결책이 있는 것 같습니다.

으아아아

테스트할 때 길이보다 큰 숫자를 사용하지 않는 것이 가장 좋습니다. 데이터가 크지 않으면 괜찮고, 그렇지 않으면 오버플로 문제를 고려해야 합니다.

Answer 3

저는 이렇게 하고 싶은데 여러분은 어떻게 생각하실지 모르겠습니다.

배열의 선두부터 시작하여 홀수를 만나면 움직이지 마세요. 짝수를 만나면 n개의 짝수가 이동할 때까지 배열의 끝에 넣으세요.

으아악

---

P.S. 왜 마이너스 점수를 주나요? 답변에 ​​문제가 있다고 생각되면 다른 사람에게 마이너스 점수를 주기 전에 먼저 댓글을 달고 토론해도 됩니다. 여기서 심각하게 토론하는 사람들을 밟을 필요는 없을 것 같습니다. . 나는 의심이 가득하다...

Answer 4

결론적으로는 불가능하다고 생각됩니다.
빠른 정렬을 사용한다고 가정하고(물론 안정성 문제를 충족하지 못합니다. 그냥 무심코 말하는 것입니다. 안정성을 원한다면 이진 트리를 사용하여 정렬할 수 있습니다) 비교 조건을 홀수로 설정하면 됩니다. 숫자는 짝수보다 크다.
그러나 일부 특별한 경우에는 정렬 문제가 O(n)일 수 있다는 것이 분명합니다.
그래서 불가능하다고 생각합니다.

Answer 5

일반적인 정렬 문제로 보면 불가능해 보일 수도 있지만 이 문제에는 세 가지 매우 까다로운 조건이 있습니다.
또한 활용할 수 있는 몇 가지 유리한 조건이 있습니다. 두 가지 중요한 사항은 다음과 같습니다.

1. 홀수는 짝수만큼 많고, 모든 배열의 길이는 n+n이다

2. 홀수와 짝수는 원래 순서를 유지하므로 크기별로 정렬할 필요가 없습니다

저는 golang을 사용하여 다음을 구현합니다.

으아악

Answer 6

원래 질문의 요구 사항은 아래에 번역되어 있습니다
1) 시간 복잡도는 선형입니다
2) 공간 복잡도는 O(k)
3) 안정적인
시간 복잡도는 O( n) 이는 비교 정렬이 더 이상 가능하지 않음을 의미합니다. 빠른 정렬 등 비교 정렬의 가장 좋은 평균 시간 복잡도는 O(nlgn)입니다.
이미 수학적으로 입증된 '알고리즘 입문'의 결론입니다.
선형 시간이 있는 유일한 것은 count, bucket 및 radix입니다. https://www.byvoid.com/blog/sort-radix를 참조하세요
즉, 정렬은
1) 계산 - 시간 복잡도입니다. O(n ) 공간 복잡도 O(k+n)

으아아아

2) 버킷 정렬 - O(n) 공간 복잡도 O(k+n)
http://www.growingwiththeweb.com/2015/06/bucket-sort.html

3) 기수 정렬 O(n) 및 O(n+k)

그래서 저는 개인적으로 이 질문에는 해결책이 없다고 생각합니다.
그런데 아래 링크를 잘 살펴보시기 바랍니다
http://bigochheatsheet.com/

저는 학교를 졸업한 지 오래되어 이러한 결정적인 사항을 명확하게 기억하지 못합니다. 즉, 위의 결정적인 사항에 대해 저는 책임을 지지 않습니다. :-)
포스터는 다음을 바탕으로 추가 증거를 제공할 수 있습니다. 위의 기사.

그러나 비교에 따른 평균 시간 복잡도는 O(nlogn)을 초과하지 않는다는 것을 확신하므로 radix, bucket sort, radix 중 어느 것이 더 가까운지 살펴보는 것이 좋습니다. 요구 사항.

Answer 7

비슷한 질문에 대한 답변은 다음과 같습니다.

https://www.quora.com/Given-an-array-of-integers-how-do-I-re-arrange-the-numbers-such-that-odd-numbers-occupy-odd-position -그리고 짝수-점유-짝수-위치

요구사항에 한 가지 차이점만 있기 때문에 문제에 대한 해결책은 동일합니다. 홀수는 홀수 인덱스 위치에 있고 짝수는 짝수 인덱스 위치에 있습니다. 링크의 첫 번째 답변은 귀하가 원하는 것에 가장 가까운 답변입니다. 단지 가까운 이유는 원본 배열이 소량의 추가 데이터를 수용할 수 있어야 하기 때문입니다.

사실 면접관이 질문할 때 명확하게 설명하지 않은 암묵적인 조건이 있을지도 의문이 듭니다. 예를 들어 2n 배열 자체가 순서 배열이라면 상황은 매우 달라질 것입니다.

Answer 8

질문을 읽고 간단히 생각해보면 다음과 같습니다.

주어진 배열인 경우 상대 순서를 변경하지 않고 유지할 수 있는 방법이 없습니다. 다음 코드는 조건 2와 3만 충족할 수 있습니다.

으아악

처음부터 끝까지 확인하시고 4가지 상황을 각각 판단하시면 됩니다.

링크드 리스트가 주어지면 위의 세 가지 조건은 쉽게 충족됩니다.

또: 아무 이유 없이 밟혔어요. . .

Answer 9

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

한 예에서 추론을 도출하는 방법에 대한 설명을 참조하세요.

논문 링크는 다음과 같습니다

《선형 시간에 따른 안정적인 최소 공간 분할》

Answer 10

해결책이 없는 것 같습니다.

이 글에서도 두 숫자의 f값을 비교하는 것은 상수 시간이라고 가정하고 있습니다. 각 숫자에는 고유한 위치 정보가 있다는 것을 이해할 수 있습니다.
http://www.diku.dk/~jyrki/Paper/KP1992bJ.pdf

다음은 No Solution에 대한 저의 분석입니다.

이 시퀀스는 길이가 n인 시퀀스에서 다른 시퀀스로 숫자의 쌍순열을 통해 최대 n-1개의 순열 연산이 필요하다는 것을 알고 있습니다. 전제는 각 숫자에 필요한 순열을 알고 있다는 것입니다. . 하지만 각 숫자가 대체될 위치를 알 수 있는 방법이 없기 때문에(저장할 장소가 없음) 각 숫자의 대체 위치를 일정한 시간에 찾을 수 있는 명확한 방법이 없습니다(실제로는 그런 건 없습니다) 방법). 그래서 이것은 불가능합니다.

추가 공간이 있는 경우 보조 어레이를 사용할 수 있습니다.
시간이 남는다면 병합 정렬과 유사한 방법, 비재귀적 구현을 ​​사용할 수 있습니다. 홀수와 짝수만 나누기 때문에 그 자리에서 교환할 수 있습니다.