網易2018校招內推編程題 等差數列

問題：

 如果一個數列S滿足對於所有的合法的i,都有S[i + 1] = S[i] + d, 這裏的d也可以是負數和零,我們就稱數列S為等差數列。

小易現在有一個長度為n的數列x,小易想把x變為一個等差數列。小易允許在數列上做交換任意兩個位置的數值的操作,並且交換操作允許交換多次。

但是有些數列通過交換還是不能變成等差數列,小易需要判別一個數列是否能通過交換操作變成等差數列 

輸入描述:

輸入包括兩行,第一行包含整數n(2 ≤ n ≤ 50),即數列的長度。

第二行n個元素x[i](0 ≤ x[i] ≤ 1000),即數列中的每個整數。

輸出描述:

如果可以變成等差數列輸出"Possible",否則輸出"Impossible"。

輸入例子1:

3

3 1 2

輸出例子1:

Possible

java程序

public class ArithmeticSequence {

	public static void main(String[] args) {

//		輸入
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int[] arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = scanner.nextInt();
		}

//		快速排序
		sortSmallToBig(arr, 0, arr.length - 1);

//		判斷差值
		int diff = arr[1] - arr[0];//先將前兩個數的差賦給變量diff
		for (int i = 2; i < arr.length; i++) {
			int temp = arr[i] - arr[i - 1]; //後續相鄰整數間的差值賦給temp
			if (temp != diff) {//若他們之間的差和前兩個差不等，說明不是等差數列，輸出Impossible 並結束程序。
				System.out.println("Impossible");
				return;
			}
		}

		System.out.println("Possible");
	}

	
//	smallToBig和sortSmallToBig是快速排序。 針對數組進行從小到大的排序。
//	調用 sortSmallToBig(int[] array, int start, int end)  傳入數組  0  和數組.lenth-1.

public static int smallToBig(int[] array, int start, int end) {
		int key = array[start];
		while (start < end) {
			while (array[end] >= key && end > start) {
				end--;
			}
			array[start] = array[end];
			while (array[start] <= key && end > start) {
				start++;
			}
			array[end] = array[start];
		}
		array[end] = key;
		return end;
	}

	public static void sortSmallToBig(int[] array, int start, int end) {
		if (start >= end) {
			return;
		}
		int local = smallToBig(array, start, end);
		sortSmallToBig(array, start, local - 1);
		sortSmallToBig(array, local + 1, end);
	}
}