首页 > itarticle > three step reverse algorithm

three step reverse algorithm

admin 11月 14, 2020 0

Three step roatating algorithm

for a array, abcdefg -> efgabcd (in place)
we can have
abcdefg -> dcbagfe -> efgabcd
this algorithm have time complexity O(n) and space complexity O(1)

Recover Rotated Sorted Array

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

Example
Example1:
[4, 5, 1, 2, 3] -> [1, 2, 3, 4, 5]
Example2:
[6,8,9,1,2] -> [1,2,6,8,9]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
class :
    """
    @param nums: An integer array
    @return: nothing
    """
    def recoverRotatedSortedArray(self, nums):
        
        for i in range(0, len(nums)-1):
            if nums[i] > nums[i+1]:
                self.reverse(nums, 0, i)
                self.reverse(nums,i+1,len(nums)-1)
                self.reverse(nums,0,len(nums)-1)
                return
                
        
    def reverse(self,nums, start, end):
        i = start
        j = end
        while i < j:
            nums[i], nums[j] = nums[j], nums[i]
            i+=1
            j-=1

Rotate String
Given a string(Given in the way of char array) and an offset, rotate the string by offset in place. (rotate from left to right)

Input: str=”abcdefg”, offset =2
Output:”fgabcde”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
class :
    """
    @param str: An array of char
    @param offset: An integer
    @return: nothing
    """
    def rotateString(self, str, offset):
        
        if len(str) == 0:
            return
        offset = offset % len(str)
        self.reverse(str, 0, len(str)-offset-1)
        self.reverse(str, len(str)-offset,len(str)-1)
        self.reverse(str, 0, len(str)-1)
                
        
    def reverse(self,nums, start, end):
        i = start
        j = end
        while i < j:
            nums[i], nums[j] = nums[j], nums[i]
            i+=1
            j-=1
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能