LintCode 39 · Recover Rotated Sorted Array.java

	// Approach #1 - 3-way flipping - T O(n), S O(1)
	public class Solution {
	/**
	* @param nums: An integer array
	* @return: nothing
	*/
	public void recoverRotatedSortedArray(List<Integer> nums) {
	// handle corner cases
	if (nums == null || nums.size() == 0) {
	return;
	}
	int n = nums.size();
	int endingIndex = n - 1;
	for (int i = 0; i < n - 1; i++) {
	if (nums.get(i) > nums.get(i + 1)) {
	endingIndex = i;
	break;
	}
	}
	// reverse left
	reverse(nums, 0, endingIndex);
	// reverse right
	reverse(nums, endingIndex + 1, n - 1);
	// reverse the whole thing
	reverse(nums, 0, n - 1);
	return;
	}
	private void reverse(List<Integer> nums, int left, int right) {
	while (left < right) {
	Integer tmp = nums.get(left);
	nums.set(left, nums.get(right));
	nums.set(right, tmp);
	left++;
	right--;
	}
	}
	}

view raw LintCode 39 · Recover Rotated Sorted Array.java hosted with ❤ by GitHub