Recover Rotated Sorted Array

Given a rotated sorted array, recover it to sorted array in-place.

 

Have you met this question in a real interview?

Yes Which company asked you this question? Airbnb Alibaba Amazon Apple Baidu Bloomberg Cisco Dropbox Ebay Facebook Google Hulu Intel Linkedin Microsoft NetEase Nvidia Oracle Pinterest Snapchat Tencent Twitter Uber Xiaomi Yahoo Yelp Zenefits Thanks for your feedback. Example

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

Challenge

In-place, O(1) extra space and O(n) time.

Clarification

What is rotated array?

For example, the orginal array is [1,2,3,4], The rotated array of it can be [1,2,3,4], [2,3,4,1], [3,4,1,2], [4,1,2,3]

 

 

 

 

1 public void recoverRotatedSortedArray(ArrayList<Integer> nums) 2 { 3 // write your code 4 if(nums.size()==0||nums.size()==1) return; 5 int i =0; 6 for(i=0; i<nums.size()-1;i++) 7 { 8 if(nums.get(i)>nums.get(i+1)) break; 9 } 10 if(i == nums.size()-1) return; 11 reverse(nums,0,i); 12 reverse(nums,i+1,nums.size()-1); 13 reverse(nums,0,nums.size()-1); 14 return; 15 16 17 } 18 19 20 public void reverse(ArrayList<Integer> nums, int left, int right) 21 { 22 while(left<right) 23 { 24 int temp = nums.get(left); 25 nums.set(left,nums.get(right)); 26 nums.set(right,temp); 27 left++; 28 right--; 29 30 } 31 32 return; 33 }

 

转载于:https://www.cnblogs.com/hygeia/p/4779854.html

相关资源：JAVA上百实例源码以及开源项目