Leetcode-notes/notes/0912/0912.py at master · PaulGuo5/Leetcode-notes · 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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
class Solution:
    def sortArray_bubble_sort(self, nums: List[int]) -> List[int]:
        # bubble sort: TLE
        if not nums: return None
        for i in range(len(nums)-1):
            for j in range(len(nums)-1, i, -1):
                if nums[j] < nums[j-1]:
                    nums[j], nums[j-1] = nums[j-1], nums[j]
        return nums

    def sortArray_selection_sort(self, nums: List[int]) -> List[int]:
        # selection sort: TLE
        if not nums: return None
        for i in range(len(nums)-1):
            min_idx = i
            for j in range(i+1, len(nums)):
                if nums[j] < nums[min_idx]:
                    min_idx = j
            if min_idx != i:
                nums[min_idx], nums[i] = nums[i], nums[min_idx]
        return nums


    def sortArray_insertion_sort(self, nums: List[int]) -> List[int]:
        # Insertion sort: TLE
        if not nums: return None
        for i in range(1, len(nums)):
            j = i
            target = nums[j]
            while j-1>=0 and target < nums[j-1]:
                nums[j] = nums[j-1]
                j -= 1
            nums[j] = target
        return nums


    def sortArray_quick_sort(self, nums: List[int]) -> List[int]:
        # quick sort
        if not nums or len(nums) == 1: return nums
        return self.quickSort(nums, 0, len(nums)-1)

    def quickSort(self, nums, left, right):
        if left >= right: return
        pivot = self.partition(nums, left, right)
        self.quickSort(nums, left, pivot-1)
        self.quickSort(nums, pivot+1, right)
        return nums

    def partition(self, nums, left, right):
        pivot_idx = left
        pivot_val = nums[left]
        while left < right:
            while right > left and nums[right] >= pivot_val:
                right -= 1
            while left < right and nums[left] <= pivot_val:
                left += 1
            nums[left], nums[right] = nums[right], nums[left]
        nums[left], nums[pivot_idx] = nums[pivot_idx], nums[left]
        return left


    def sortArray_counting_sort(self, nums: List[int]) -> List[int]:
        # counting sort: O(n)
        positive = [n for n in nums if n>=0]
        negative = [-n for n in nums if n<0]
        pp = self.countSort(positive)
        nn = self.countSort(negative)
        pp = [] if not pp else pp
        nn_re = [-n for n in nn][::-1] if nn else []
        return nn_re + pp

    def countSort(self, nums):
        if not nums: return None
        b = [0 for i in range(len(nums))]
        c = [0 for i in range(max(nums)+1)]
        for n in nums:
            c[n] += 1
        for i in range(1, len(c)):
            c[i] += c[i-1]
        for n in nums:
            b[c[n]-1] = n
            c[n] -= 1
        return b


    def sortArray_bucket_sort(self, nums: List[int]) -> List[int]:
        # bucket sort: O(nlogn)
        if not nums: return None
        def bucketSort(nums):
            max_, min_ = max(nums), min(nums)
            buckets = [0 for _ in range(max_-min_+1)]
            for i in range(len(nums)):
                buckets[nums[i]-min_] += 1
            res = []
            for i in range(len(buckets)):
                res += buckets[i] * [i+min_]
            return res
        return bucketSort(nums)


    def sortArray(self, nums: List[int]) -> List[int]:
        # Radix sort O(n*m)
        def radixSort(nums, d):
            for i in range(d):
                s = [[] for _ in range(10)]
                for n in nums:
                    s[n//(10**i)%10].append(n)
                nums = [n for b in s for n in b]
            return nums

        positive = [n for n in nums if n >= 0]
        negative = [-n for n in nums if n < 0]
        if positive:
            p_res = radixSort(positive, len(str(max(positive))))
        else: return n_res
        if negative:
            n_res = [-n for n in radixSort(negative, len(str(max(negative))))][::-1]
        else: return p_res
        return n_res + p_res