伊谢尔伦2017-04-17 18:00:17
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.
reply
0
