Peaks and Valleys: In an array of integers, a “peak” is an element which is greater than or equal to the adjacent integers and a “valley” is an element which is less than or equal to the adjacent integers. For example, in the array {5, 8, 6, 2, 3, 4, 6}, {8, 6} are peaks and {5, 2} are valleys. Given an array of integers, sort the array into an alternating sequence of peaks and valleys.
EXAMPLE
1
2
|
Input: {5, 3, 1, 2, 3}
Output: {5, 1, 3, 2, 3}
|
Hints: #196, #219, #231, #253, #277, #292, #316
解法1
什么是Peak？ >= 左右两边的数字就是Peak。
什么是Valley？<= 左右两边的数字就是Valley。
给你一个数组，对它排序，使得它的Peak和Valley交替。换句话说就是{大、小、大、小}这样。
现在看一个已经排序好的数组：
那么我们可以从左右两边向中间取元素，交替放置：
1
2
|
a5, a1
a5, a1, a4, a2, a3
|
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
public int[] peakValleys(int[] array) {
int[] result = new int[array.length];
Arrays.sort(array);
int head = 0;
int tail = array.length - 1;
int i = 0;
while (head < tail) {
result[i] = array[tail];
tail--;
i++;
result[i] = array[head];
head++;
i++;
}
if (head == tail) {
result[i] = array[head];
}
return result;
}
|
解法2
有没有办法不对数组做排序来弄？可以弄一个指针从index 1开始遍历，在两个检查模式中切换：
- 当前元素比前一个元素小
- 当前元素比前一个元素大
如果检查结果为false，那么就将当前元素和前一个元素交换
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
mode_lt = check(a[i] < a[i - 1]) == true
mode_gt = check(a[i] > a[i - 1]) == true
Round 1: mode_lt, check pass
v
5, 3, 1, 2, 3
Round 2: mode_gt, check fail, swap
v
5, 3, 1, 2, 3 -> 5, 1, 3, 2, 3
Round 3: mode_lt, check pass
v
5, 1, 3, 2, 3
Round 4: mode_gt, check pass
v
5, 1, 3, 2, 3
|
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
public void peakValley(int[] array) {
if (array.length <= 1) {
return;
}
int mode = MODE_LT;
for (int i = 1; i < array.length; i++) {
if (mode == MODE_LT) {
if (!(array[i] < array[i - 1])) {
swap(array, i, i - 1);
}
mode = MODE_GT;
} else {
if (!(array[i] > array[i - 1])) {
swap(array, i, i - 1);
}
mode = MODE_LT;
}
}
}
private void swap(int[array], int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
|
评论