阿里算法笔试题降序数组重排，求答案

我做了一下，感觉应该是对的，前n/2数据改变后新坐标为j=2*i+1,后n/2数据为j=2*(n-i-1)，然后这样更新数组就行了，每次用一个temp，时间O（N），空间O（1）

#include<cstdio> using namespace std; const int maxn=100010; int n,a[maxn]; int main(){ while(~scanf("%d",&n)){ for(int i=1;i<=n;i++){ a[i]=n-i+1; } for(int i=1;i<=n;i++){ if(a[i]>n) continue; else{ int k=i,j=-1,tmp=a[i]+n; tmp-=n; if(tmp>(n+1)/2) j=2*(n-tmp+1); else j=2*tmp-1; int num=a[j]; a[j]=tmp+n; tmp=num+n; k=j; while(k!=i){ tmp-=n; if(tmp>(n+1)/2) j=2*(n-tmp+1); else j=2*tmp-1; num=a[j]; a[j]=tmp+n; tmp=num+n; k=j; } } } for(int i=1;i<=n;i++){ printf("%d ",a[i]-n); } printf("\n"); } } 这个代码是时间复杂度O(n)，空间复杂度O(1)的做法。

类似于冒泡排序，不过只要一遍就行了，因为我们在swap之前就知道每个值排完序之后对应的是哪个位置，所以我们就不断的 swap(当前最大值,排完序后的位置） 一遍就能解决。

下标 1 2 3 4 5 6 7 值 7 6 5 4 3 2 1 变换之后 在原数组中的下标 4+3 4-3 4+2 4-2 4+1 4-1 4 值 1 7 2 6 3 5 4 其中4是数组中间节点

任何一个n元置换都可以表示成几个对换的乘积——《近代代数初步》 比如， n=2时， 置换为（1-2-1） n=3时， 置换为（1-3-2-1） n=4时， 置换为（1-4-2-1）（3-3） n=5时， 置换为（1-5-3-4-2-1） n=6时， 置换为（1-6-3-5-4-2-1） n=7时，置换为（1-7-4-2-1）（3-6）（5-5）

最优做法确实应该是先算出每个元素的最终位置，比如7的最终位置是6。然后继续处理6这个位置原有数字6的位置，6的位置是4，然后继续找位置4的这个数字的最终位置，位置4的数字是4，它的最终位置是1，然后7这个位置的数字是1，它的位置是1。这样我们处理的过程就是7->6->4->1->7，7覆盖6,6覆盖4,4覆盖1,1覆盖7，就会形成一个环。5->2->5，3->3也会形成环。然后这样的话就可以解决双指针覆盖数字的问题。时间复杂度 O(n)，空间复杂度O(1)。

#include<cstdio> #include<queue> using namespace std; int a[1000010],n; int main(){ while(~scanf("%d",&n)){ for(int i=1;i<=n;i++){ a[i]=n-i+1; } int i=1,j=n,k=0; deque<int> q; int res=0; while(i<=j){ if(!k){ q.push_back(a[i]); int sz=q.size(); res=max(res,sz); a[i]=a[j]; i++,j--; }else{ int top=q.front(); q.pop_front(); int tmp=a[i]; a[i]=top; q.push_back(tmp); int sz=q.size(); res=max(res,sz); i++; } k=k^1; } if(a[i-1]==q.back()) q.pop_back(); while(!q.empty()){ if(!k){ int top=q.back(); q.pop_back(); a[i]=top; i++,k=k^1; }else{ int top=q.front(); q.pop_front(); a[i]=top; i++,k=k^1; } } for(int i=1;i<=n;i++){ printf("%d ",a[i]); } printf("\n"); } } 时间复杂度O(n)肯定没问题。 如果n很小的话，队列元素很少，空间复杂度可以看成是常数级别O(1)。 如果n为10^6级别的话，则队列最大元素个数可用res那个变量求出，大概在3*10^5左右。n为10^5, 则res为3*10^4左右。。 总之就是双指针在使用的过程中，覆盖的元素会越来越多，因而只能用队列来保存。如果n为10^6级别， 纯O(1)做法，不会覆盖别的元素的做法还真没想出来。

两个指针一个指向最开始，一个指向最后，一个一个的选不就ok了，

完美洗牌

同问