阿里2016-09-09校招笔试附加题--难度有点大

初步想法可以从最后一个数字开始，不断调整到正确的位置。比如7654321，先看1，计算出应该换到第0个位置，此时7就到最后了，再看7算出应该换到第1个位置，依此类推。发现要换过去的位置就是当前位置的再看下一个（左边的）数。要保存的只有当前操作数是第几大和所在索引两个变量。

据说是完美洗牌问题

/*采用类似于间接排序的中间置换法思想 1.每次存储i处元素0，i为hole，然后找到i应该存储的元素p，将其移至i，然后p为hole， 然后找到p处应该存储的元素并放入p处。。。知道空洞出应该存储V[i]。 2.移动元素时需要将元素变为负值，防止已经移动的元素再次被移动。 3.接收后将每个元素改为正。 4.复杂度O(N),最多两个元素交换3次，总共最多交换3N/2 */ //获取i处应该存放的元素下标 int getposition(int i, int n) { if(i%2 == 0) return n - 1 - i / 2; else return (i + 1) / 2 - 1; } void fun(vector<int> &v) { for (int i = 0; i < v.size(); ++i) { if(v[i] < 0) continue; cout << i << endl; int p = getposition(i, v.size()); int tmp = -v[i]; int hole, nextHole = p; for (hole = i; p != i; hole = nextHole) { nextHole = p; v[hole] = -v[p]; p = getposition(p, v.size()); } v[nextHole] = tmp; //遇见首次腾出位置的元素v[i]，将其放入空位 cout << v[i] << endl; } for(auto &i : v) i = -i; }

知乎上有相关讨论：https://www.zhihu.com/question/50512830 def minmax_sort(A): n = len(A) def index(i): ''' 根据观察得到原数组和变换后的数组下标关系， 这里考虑下标从1开始 ''' if i<=n/2: return 2*i return (2*n-2*i+1)%(n+1) A = A for ii in xrange(1,n+1): prev = A[ii-1] if prev<0:#判断是否已经循环过了 continue save,i = ii,ii while True: ''' 关键部分，下标index(index(i)) 嵌套会成为一个环，环之间不交叉， 对每个环将数放到它应该在的位置 ''' i = index(i) cur = A[i-1] A[i-1] = -prev #标记该位置已经被置换过了 prev = cur if save==i: #回到循环起点 break for i in xrange(n): #回正 A[i] *=-1 print(A) return A a = range(8,0,-1) minmax_sort(a)