等差数列——网易

• 如果一个数列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");
    }
}