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

매우 간단합니다
계산 정렬 사용
숫자 범위가 0에서 65535 사이라고 가정하고 배열 count[65536]를 정의합니다(이 공간은 상수이고 n과 관련이 없으므로 O(1 )), 초기값은 모두 0이다.
다음 숫자가 있다고 가정합니다.
100
200
300
119
0
6
...
그런 다음 각 숫자에 대해 모두 개수로 기록하세요.
100 => 개수[100]++
200 => 개수[200]++
300 => 개수[300]++
119 => 개수[ 119]++
0 => count[0]++
6 => count[6]++
...
즉,
먼저 이 숫자를 모두 순회하세요. (카운트 배열에서) 0부터 65535까지의 각 숫자의 수를 얻으려면
그런 다음 , count[n] = m 순서로 카운트 배열을 순회한 다음 m n을 출력합니다(예: count[3] = 2이면 숫자가 2개가 있다는 의미입니다. 3) 이를 순차적으로 출력하고 최종적으로 결과를 얻습니다.
출력 시:
먼저 홀수 count[1], count[3]...
그 다음 짝수 count[0],count[2]...
출력 :
첫 번째 순회는 O(n)이고 두 번째 순회는 O(1)이며 이는 상수이므로 최종 시간 복잡도는 O(n)이고 공간 복잡도는 O(1)입니다

PS: 이 알고리즘은 매우 간단합니다. 누구나 할 수 있다고 믿습니다. 하지만 이 질문은 너무 왜곡되어 있어 일반적으로 면접관을 놀라게 할 것입니다.

Answer 2

O=원본 목록

N=[없음]*2n
O의 경우:

으아악

가장 큰 문제는 공간입니다. 2n 공간을 차지하지 않고서는 불가능합니다. 상황이 복잡하기 때문에, 일정한 공간이 충분하다고 판단하는 것은 불가능합니다!

Answer 3

으아아아

js 구현은 짝수인 경우 하나가 해제된 다음 끝에 추가되고 초기 배열의 마지막 항목이 처리될 때 중지됩니다. moling3650의 이전 코드를 참고하세요. .

Answer 4

@白丁을 좋아했는데 누군가 즉시 비추천했습니다
어떤 사람들은 n-1 공간을 신청한 후 공간 복잡도가 일정하지 않다고 생각할 수도 있습니다.
확인하기 위해 PHP를 사용했습니다. 실제로 증가된 메모리는 php5.4에서 테스트한 증가된 메모리 양입니다.

으아아아

Answer 5

시간 복잡도가 O(n)인 정렬이 있나요?

Answer 6

댓글들을 보고 처음엔 답이 없는 줄 알았는데, 오늘 퇴근길에 문득 생각이 나서 방법이 생각났는데, 잠깐 확인해보니 정말 그렇네요. 가능한.
이 알고리즘에는 O(1) 공간과 O(n) 시간만 필요하며 원래 배열에서 홀수와 짝수의 상대적 순서를 변경하지 않으므로 질문의 요구 사항을 완전히 충족합니다. 오늘은 알고리즘 아이디어에 대해 먼저 이야기하고, 내일은 프로그램을 완성하는 시간을 갖도록 하겠습니다.

간단히 말하면 각 요소를 앞에서 뒤로 스캔합니다. 스캔할 때 두 개의 포인터가 사용되며, 하나는 일반 순회에 사용됩니다(우리가 일반적으로 배열을 순회하는 데 사용하는 i 입니다). 배열의 첫 번째 항목을 가리킵니다. 여기서는 偶数指针이라고 하는 짝수는 -1으로 초기화됩니다.

순회가 시작됩니다. 각 요소에 대해 다음과 같은 상황으로 구분됩니다.

1. 요소가 홀수이고 그 앞에 짝수가 있습니다(짝수 포인터가 0보다 크거나 같음). 이 두 숫자를 교환하세요

2. 요소가 홀수이고 그 앞에 짝수가 없으며(짝수 포인터는 -1) 아무 작업도 수행되지 않고 다음 순회 라운드가 계속됩니다

3. 요소가 짝수이고 이전 요소가 짝수입니다(짝수 포인터가 가리키는 요소가 아니라 이전 요소라는 점에 유의하세요). 이 두 숫자를 교환하세요

4. 요소는 짝수이고 이전 요소는 홀수입니다. 이때 짝수 포인터는 -1이어야 하며 이를 현재 요소의 인덱스(예: i)에 할당해야 합니다. )

이것은 두 번째 요소까지 반복되며 마지막 요소에는 특별한 처리가 필요합니다. 홀수이면 위의 단계를 따릅니다. 1 짝수이면 처리가 수행되지 않고 순회가 이루어집니다. 완전한. .

예를 들어 1 2 3 4 5 6의 경우 다음은 각 순회 라운드 후 배열의 상태입니다([]는 현재 순회된 요소와 짝수 포인터가 가리키는 요소를 나타냄).

[1] 2 3 4 5 6
1 [2] 3 4 5 6
1 3 [2] 4 5 6
1 3 [4] [2] 5 6
1 3 5 [2] [4] 6
1 3 5 [2] 4 [6] // 완료

또 다른 예, 1 2 4 6 8 5 7 3:

[1] 2 4 6 8 5 7 3
1 [2] 4 6 8 5 7 3
1 [4] [2] 6 8 5 7 3
1 [4] 6 [ 2] 8 5 7 3
1 [4] 6 8 [2] 5 7 3
1 5 [6] 8 2 [4] 7 3
1 5 7 [8] 2 4 [6] 3
1 5 7 3 [2] 4 6 [8] // 완료

Answer 7

맙소사, JavaScript가 세계 최고의 언어라는 것이 즉시 명백해졌습니다

배열은 연결 리스트이고 다양한 연산을 지원합니다. 젠장

보충: 내 말에 신경 쓰지 마세요. PHP는 세계 최고의 언어입니다. 제가 틀렸습니다

추가 참고 사항: 내가 데이터 구조를 이해하지 못한다고 말하는 사람들은 아마도 내 놀리는 말투를 이해하지 못할 것입니다...