LeetCode-Solutions/Python/rotate-non-negative-elements.py at master · kamyu104/LeetCode-Solutions · GitHub

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
# Time:  O(n)
# Space: O(n)

# array
class Solution(object):
    def rotateElements(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        def gcd(a, b):
            while b:
                a, b = b, a%b
            return a

        def rotate(nums, k):
            k %= len(nums)
            c = gcd(len(nums), k)
            for i in xrange(c):
                for j in xrange(1, len(nums)//c):
                    nums[i], nums[(i-j*k)%len(nums)] = nums[(i-j*k)%len(nums)], nums[i]

        result = [x for x in nums if x >= 0]
        if not result:
            return nums
        rotate(result, k)
        j = 0
        for i in xrange(len(nums)):
            if nums[i] < 0:
                continue
            nums[i] = result[j]
            j += 1
        return nums


# Time:  O(n)
# Space: O(n)
# array
class Solution2(object):
    def rotateElements(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        def reverse(nums, left, right):
            while left < right:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1

        def rotate(nums, k):
            k %= len(nums)
            reverse(nums, 0, len(nums)-1)
            reverse(nums, 0, len(nums)-k-1)
            reverse(nums, len(nums)-k, len(nums)-1)

        result = [x for x in nums if x >= 0]
        if not result:
            return nums
        rotate(result, k)
        j = 0
        for i in xrange(len(nums)):
            if nums[i] < 0:
                continue
            nums[i] = result[j]
            j += 1
        return nums


# Time:  O(n)
# Space: O(n)
# array
class Solution3(object):
    def rotateElements(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        def reverse(nums, left, right):
            while left < right:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1

        def rotate(nums, k):
            k %= len(nums)
            nums[:] = nums[k:]+nums[:k]

        result = [x for x in nums if x >= 0]
        if not result:
            return nums
        rotate(result, k)
        j = 0
        for i in xrange(len(nums)):
            if nums[i] < 0:
                continue
            nums[i] = result[j]
            j += 1
        return nums