L1-恢复旋转排序数组

Posted on | In |

题目描述：

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

什么是旋转数组？

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

挑战：使用O(1)的额外空间和O(n)时间复杂度

法一

假设1前面有k个数,找到1的位置后, 将其前面的k个数增加到数组末尾,然后数据统一前移一次,再去除后面的k个位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    /**
     * @param nums: An integer array
     * @return: nothing
     */
    public void recoverRotatedSortedArray(List<Integer> nums) {
        // write your code here
        int temp=nums.get(0);
        int length=nums.size();
        int i;
        for( i=0;i<length;i++)
        {
            if(nums.get(i)<temp)
                break;  
        }
         for(int j=0;j<i;j++)
        nums.add(nums.get(j));
   nums.subList(0, i).clear();
      }
}

法二：三步翻转法

三步翻转法：以{4,5,6,7,1,2,3}为例

  1. 先找到1的位置.然后翻转{4,5,6,7}得到{7,6,5,4}

  2. 翻转{1,2,3}得到{3,2,1}

  3. 此时数组为：{7,6,5,4,3,2,1}, 将其翻转即得{1,2,3,4,5,6,7}

即前半部分逆序，后半部分逆序，整体再逆序

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
26
27
28
29
30
31
32
33

import java.util.*;
public class Solution {
    /**
     * @param nums: An integer array
     * @return: nothing
     */
	public void reverse(List<Integer> nums,int start,int end)
	{
		while(start<end)
		{
		int temp=nums.get(start);
		nums.set(start, nums.get(end));
		nums.set(end, temp);
		start++;
		end--;
	}
	}
    public void recoverRotatedSortedArray(List<Integer> nums) {
        // write your code here
        int temp=nums.get(0);
        int length=nums.size();
        int i;
        for( i=0;i<length-1;i++)
        {
            if(nums.get(i)>nums.get(i+1))
            	break;
        }
         reverse(nums, 0, i);
         reverse(nums, i+1, length-1);
         reverse(nums, 0, length-1);
    }
}