恢复旋转排序数组

题意

给定一个旋转排序数组,在原地恢复其排序。

什么是旋转数组?

比如,原始数组为[1,2,3,4], 则其旋转数组可以是[1,2,3,4], [2,3,4,1], [3,4,1,2], [4,1,2,3]

样例

[4, 5, 1, 2, 3] -> [1, 2, 3, 4, 5]

思路

遍历数组,首先找到当前数大于下一个数的位置,也就是样例中的 5,然后将数组开头的元素到 5 进行翻转,结果是 [5, 4, 1, 2, 3],然后将后面的元素进行翻转,结果是 [5, 4, 3, 2, 1],再将整个数组翻转,就得到了最终结果。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
/**
* @param nums: The rotated sorted array
* @return: The recovered sorted array
*/
public void recoverRotatedSortedArray(List<Integer> nums) {
for (int i = 0; i < nums.size() - 1; i++) {
if (nums.get(i) > nums.get(i + 1)) {
reverse(nums, 0, i);
reverse(nums, i + 1, nums.size() - 1);
reverse(nums, 0, nums.size() - 1);
return;
}
}
}

public void reverse(List<Integer> list, int start, int end) {
for (int i = start, j = end; i < j; i++, j--) {
int temp = list.get(i);
list.set(i, list.get(j));
list.set(j, temp);
}
}
};

原题地址

LintCode:恢复旋转排序数组

坚持原创技术分享,您的支持将鼓励我继续创作!