Question

link

输入一个数组，要求输出满足：a[0]<=a[1]>=a[2]<=a[3]>=…

Solution

O(n)，一边扫描即可。发现不符合条件的只要跟前面一个数对调就可以，

Code

public int[] solve(int[] input) {
	boolean incr = true;
	int len = input.length;
	int p = 1;
	while (p < len) {
		if (incr ^ (input[p - 1] < input[p])) {
			Common.swap(input, p - 1, p);
		}
		p++;
		incr = !incr;
	}
	return input;
}