- 如果一个数列S满足对于所有的合法的i,都有S[i + 1] = S[i] + d, 这里的d也可以是负数和零,我们就称数列S为等差数列。
小易现在有一个长度为n的数列x,小易想把x变为一个等差数列。小易允许在数列上做交换任意两个位置的数值的操作,并且交换操作允许交换多次。但是有些数列通过交换还是不能变成等差数列,小易需要判别一个数列是否能通过交换操作变成等差数列
题目大意：
-
判断一个数列是否是等差数列，因此该题的优化主要集中在Top 2问题上面。
- parition算法：O(n)
- 优先队列：O(nlog2)
- 排序：O(nlogn)
该题还有一种有bug的做法，采用等差数列求和公式，时间复杂度虽然同样达到O(n),但是明显更快，因为是真正的O(n),只需扫描一遍。
bug主要是，sum虽然可以和等差数列的和一样，但是不能证明该数列是等差数列。
虽然该解法可以通过OJ，显然是OJ测试用例不足。
Code
public class DisArr {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int a[] = new int[n];
for (int i = 0; i < n; ++i)
{
a[i] = scanner.nextInt();
}
scanner.close();
Arrays.sort(a);
int dis = a[1] - a[0];
for (int i = 1; i < a.length; ++i)
{
if (a[i] - a[i - 1] != dis)
{
System.out.println("Impossible");
return;
}
}
System.out.println("possible");
}
}
