题目:
恢复旋转排序数组
给定一个旋转排序数组,在原地恢复其排序。
样例
[4, 5, 1, 2, 3]
-> [1, 2, 3, 4, 5]
挑战
使用O(1)的额外空间和O(n)时间复杂度
说明
什么是旋转数组?
- 比如,原始数组为[1,2,3,4], 则其旋转数组可以是[1,2,3,4], [2,3,4,1], [3,4,1,2], [4,1,2,3]
解题:
开始我想,先找到中间的临界点,然后在排序,临界点找到了,排序不知道怎么搞了,在这里,看到了很好的方法,前半部分逆序,后半部分逆序,整体再继续。
Java程序:
public class Solution {
/**
* @param nums: The rotated sorted array
* @return: void
*/
public void recoverRotatedSortedArray(ArrayList<Integer> nums) {
// write your code
int numslen = nums.size();
int i=0;
for(i=0;i<numslen-1;i++){
if(nums.get(i)>nums.get(i+1)){
reverse(nums,0,i);
reverse(nums,i+1,numslen-1);
reverse(nums,0,numslen-1);
}
} }
public void reverse(ArrayList<Integer> nums,int start,int end){
while(start<end){
int tmp = nums.get(start);
nums.set(start,nums.get(end));
nums.set(end,tmp);
start++;
end--;
}
}
}
总耗时: 1414 ms
然后我看到网上用的都是这个方法。。。。
Python程序:
class Solution:
"""
@param nums: The rotated sorted array
@return: nothing
"""
def recoverRotatedSortedArray(self, nums):
# write your code here
if nums==None:
return
numslen = len(nums)
for index in range(numslen-1):
if(nums[index]>nums[index+1]):
self.reverse(nums,0,index)
self.reverse(nums,index+1,numslen-1)
self.reverse(nums,0,numslen-1) def reverse(self,nums,start,end):
while start<end:
self.swap(nums,start,end)
start+=1
end-=1 def swap(self,nums,start,end):
tmp = nums[start]
nums[start] = nums[end]
nums[end] = tmp
总耗时: 228 ms