接着
@Milo Yip的思路:扫一遍可以确定首末项及公差,假如输入的数列是一个等差数列,这时给出数列中任意一个元素的值就可以求出它在将数列排序后会位于第几项。如果了解置换群的话,说到这里应该就能想到O(1)额外空间的做法了~
代码用纯C写的。请各位把重点放在算法本身而非实现细节上。
#include <stdio.h> #define LEN 1000 int a[LEN]; int main(){ int n, i; scanf("%d", &n); for(i = 0; i < n; i++) scanf("%d", &a[i]); //find min & max and compute delta int min = a[0], max = a[0]; for(i = 1; i < n; i++){ if(min > a[i]) min = a[i]; if(max < a[i]) max = a[i]; } int delta = (max - min) / (n - 1); //try to sort the sequence int q; for(q = 0; q < n; q++) while(a[q] != min + q * delta){ int pos, tmp; pos = (a[q] - min) / delta; if((a[q] - min) % delta != 0 || a[pos] == a[q]) break; tmp = a[pos]; a[pos] = a[q]; a[q] = tmp; } printf("%s
", q == n? "True": "False"); return 0; }