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

It’s very simple
Use counting to sort
Assume that your number range is from 0 to 65535, define an array count[65536] (this space is a constant, has nothing to do with n, so it is O(1)), the initial value is all is 0.
Suppose there are the following numbers:
100
200
300
119
0
6
...
Then for each number, record it in count:
100 => count[100]+ +
200 => count[200]++
300 => count[300]++
119 => count[119]++
0 => count[0]++
6 => count[6]++
...
In other words:
First, traverse all these numbers to get the number of each number from 0 to 65535 (in the count array)
Then, traverse count in order Array, count[n] = m, then output m n's (for example, count[3] = 2, then it means there are two numbers 3), output them in sequence, and finally get the result. When outputting:
First output odd numbers count[1], count[3]...
Then output even numbers count[0], count[2]...
Complexity analysis:
The first traversal is O( n), the second traversal is O(1), which is a constant, so the final time complexity is O(n), and the space complexity is O(1)

PS: This algorithm is very simple, I believe everyone can do it, but this question is too perverted and will usually scare the interviewer

Answer 2

O=orgin list

N=[None]*2n
for i in O:

odd=0
even=n
if int(i/2)==i/2:
    N[even]=i
    even+=1
else:
    N[odd]=i
    odd+=1

The main problem is space. It should not be possible without occupying a 2n space. Because the situation is complicated, it is impossible to determine that constant space is enough!

Answer 3

var l = [1, 2, 4, 6, 3, 5]
var i=0, item, last = l[l.length-1], count=0;
while(i<l.length){
  count++;
  item = l[i];
  if(item == last){
    break;
  }
  if(item % 2 == 0){
    l.splice(i, 1);
    l.push(item);
  }else{
    i++;
  }
}
console.log(count); //循环执行了多少次
console.log(l); //最后结果

The js implementation should be like this. When there is an even number, one is released, then appended to the end, and stops when the last one of the initial array is processed. Refer to the previous code of moling3650. .

Answer 4

I just liked @白丁 and someone immediately downvoted it
Some people may think that the space complexity is not constant after applying for n-1 spaces.
I used php to output to verify. In fact, the increased memory is a constant. The increased memory amount in the php5.4 test is: 160

<?php
$arr = range(1,20);  //生成1-20组成的数组
$n = count($arr); //统计数组个数
$old = memory_get_usage(); //统计页面占用内存

/* 开始处理数组 */
for($i=0;$i<$n;$i++){
    if($arr[$i]%2==0){
        $arr[] = $arr[$i];
        unset($arr[$i]);
    }
}
/* 处理结束 */

echo memory_get_usage()-$old; //输出当前占用内存减去原来内存，修改前面数组个数range(1,20)，range(1,20000)等，这里输出值固定为：160

var_dump($arr); //输出数组，数组下标到了3n-1,可能会觉得申请了n-1的空间

Answer 5

Is there a sorting with time complexity of O(n)

Answer 6

After reading the comments, I thought this question had no solution at first, but on my way to get off work today, I suddenly had an idea and thought of a method. After a brief verification, I found that it is indeed possible.
This algorithm only takes O(1)的空间，O(n) time and will not change the relative order between odd numbers and even numbers in the original array, which fully meets the requirements of the question. Today I will talk about the algorithm idea first, and I will take the time to complete the program tomorrow.

Simply put, it scans each element from front to back. When scanning, two pointers are used, one is used for regular traversal (which is what we usually use to traverse the array. i）；另一个始终指向数组中的第一个偶数，这里称为偶数指针，初始化为-1

The traversal starts. For each element, it is divided into the following situations:

1. The element is an odd number, and there is an even number before it (the even pointer is greater than or equal to

   ), exchange these two numbers0

2. The element is an odd number, and there is no even number before it (the even pointer is

   ), no operation is performed, and the next round of traversal continues-1

3. The element is an even number, and its previous element is an even number (note that it is the previous element, not the element pointed to by the even pointer), exchange these two numbers

4. The element is an even number, and its previous element is an odd number. At this time, the even pointer must be

   , and assign it to the index of the current element (i.e. i)-1，将其赋值为当前元素的索引（即i

This is repeated until the penultimate element, and the last element requires special processing: if it is an odd number, follow the steps above

; if it is an even number, no processing is done, and the traversal is completed. 1

For example, 1 2 3 4 5 6, the following is the state of the array after each round of traversal (

represents the element currently traversed and the element pointed to by the even pointer): []

[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] // Done

Another example, 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] // Done

Answer 7

Holy shit, it instantly became clear that JavaScript is the best language in the world

Array is a linked list, supports various operations, Wow

Supplement: Don’t pay attention to me, PHP is the best language in the world, I was wrong

Another addition: Those who say I don’t understand data structures probably don’t get my ridicule...