[剑指Offer] Day 17: Sorting

Authored by Tony Feng

Created on April 28th, 2022

Last Modified on April 28th, 2022

Task 1 - Q40. 最小的k个数

Question

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

Solution 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        def quickSort(arr, l, r):
            if l >= r:  # len(subarray) == 1
                return
            
            i, j = l, r
            while i < j:
                while i < j and arr[j] >= arr[l]: 
                    j -= 1
                while i < j and arr[i] <= arr[l]: 
                    i += 1
                arr[i], arr[j] = arr[j], arr[i]
            arr[l], arr[i] = arr[i], arr[l] # arr[l] is the base number and needs to separate two sub-arrays

            quickSort(arr, l, i - 1)
            quickSort(arr, i + 1, r)
        
        quickSort(arr, 0, len(arr)-1)
        return arr[:k]

Solution 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        if k >= len(arr): 
            return arr

        def quickSort(l, r):
            i, j = l, r
            while i < j:
                while i < j and arr[j] >= arr[l]: 
                    j -= 1
                while i < j and arr[i] <= arr[l]: 
                    i += 1
                arr[i], arr[j] = arr[j], arr[i]
            arr[l], arr[i] = arr[i], arr[l]

            if k < i: 
                return quickSort(l, i - 1) 
            elif k > i: 
                return quickSort(i + 1, r)
            else:
                return arr[:k]
            
        return quickSort(0, len(arr) - 1)

Explanation

Solution 1
- Time Complexity: O(N * log(N)), i.e., quick sort
- Space Complexity: O(N), i.e., the worst case is the input array is in descending order.
Solution 2
- Time Complexity: O(N), i.e., Every time only one side will be processed, N + N/2 + N/4 + N/8 + …
- Space Complexity: O(log(N)), i.e., Average recursion depth is log(N).

Task 2 - Q41. 数据流中的中位数

Question

如何得到一个数据流中的中位数？设计一个支持以下两种操作的数据结构：

void addNum(int num): 从数据流中添加一个整数到数据结构中。
double findMedian(): 返回目前所有元素的中位数。

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


import heapq
class MedianFinder:
    def __init__(self):
        self.large = [] # A half of larger elements and the top is the smallest in the heap
        self.small = [] # A half of smaller elements and the top is the bigest in the heap
        heapq.heapify(self.large)
        heapq.heapify(self.small)

    def addNum(self, num: int) -> None:
        if len(self.large) == len(self.small): # Even number of elements
            heapq.heappush(self.small, -num)
            n = -heapq.heappop(self.small)
            heapq.heappush(self.large, n)
        else: # Odd number of elements
            heapq.heappush(self.large, num)
            n = heapq.heappop(self.large)
            heapq.heappush(self.small, -n)

    def findMedian(self) -> float:
        if len(self.large) == len(self.small):
            return (self.large[0] - self.small[0])/2 # Find the top elements of two heaps
        else:
            return self.large[0]

Explanation

heapq pops only smallest number, so number should be inversed before stored into self.small.
Time Complexity
- findMedian: O(1)
- addNum: O(log(N))
Space Complexity: O(N)