伊谢尔伦2017-04-17 18:00:17
用链表还是很容易的吧，只是改变指针就可以了，遍历一次搞定，遇到偶数插入队尾（只改指针不申请内存），奇数就不管它，但如果还要对奇偶数各自排序基本不会有O(n)的算法
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;
}
已经很多人说了， 用链表是很容易实现的，但是用数组却不行（保持稳定性，时间O(n)，空间O(1)），如果谁可以，show your code，让我们膜拜你。
初看无解的问题，貌似也有解决的办法的，待我整理一下。
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
最好不要用大于length数字来测试，如果数据不大的话，应该没问题的，否则就要考虑溢出的问题了。
Antwort
0
