<jupyter_start><jupyter_text>"Pattern 17: Kth Smallest Number"> - toc: true - badges: true- comments: false- categories: [Algorithm Pattern] **Problem Statement:**Given an `unsorted array` of numbers, find Kth smallest number in it.Please note that it is the Kth smallest number in the sorted order, not the Kth distinct element.`Example 1:`**Input:** [1, 5, 12, 2, 11, 5],  K = 3**Output:** 5**Explanation:** The 3rd smallest number is '5', as the first two smaller numbers are [1, 2].`Example 2:`**Input:** [1, 5, 12, 2, 11, 5], K = 4**Output:** 5**Explanation:** The 4th smallest number is '5', as the first three smaller numbers are[1, 2, 5].`Example 3:`**Input:** [5, 12, 11, -1, 12], K = 3**Output:** 11**Explanation:** The 3rd smallest number is '11', as the first two small numbers are [5, -1].  1. Sort<jupyter_code>def find_Kth_smallest_number(nums, k):
  return sorted(nums)[k-1]


def main():

  print("Kth smallest number is: " +
        str(find_Kth_smallest_number([1, 5, 12, 2, 11, 5], 3)))

  # since there are two 5s in the input array, our 3rd and 4th smallest numbers should be a '5'
  print("Kth smallest number is: " +
        str(find_Kth_smallest_number([1, 5, 12, 2, 11, 5], 4)))

  print("Kth smallest number is: " +
        str(find_Kth_smallest_number([5, 12, 11, -1, 12], 3)))


main()<jupyter_output>Kth smallest number is: 5
Kth smallest number is: 5
Kth smallest number is: 11<jupyter_text>**Time & Space Complexity:**Sorting will take `O(NlogN)` and if we are not using an in-place sorting algorithm, we will need `O(N)` space.  2. Max Heap> 在`大顶堆`中维持`K`个最小的元素。放入、取出时都加负号即可实现大顶堆。<jupyter_code>from heapq import *


def find_Kth_smallest_number(nums, k):
  maxHeap = []
  # put first k numbers in the max heap
  for i in range(k):
    heappush(maxHeap, -nums[i])

  # go through the remaining numbers of the array, if the number from the array is smaller than the
  # top(biggest) number of the heap, remove the top number from heap and add the number from array
  for i in range(k, len(nums)):
    if nums[i] < -maxHeap[0]:
      heappop(maxHeap)
      heappush(maxHeap, -nums[i])

  # the root of the heap has the Kth smallest number
  return -maxHeap[0]
def main():

  print("Kth smallest number is: " +
        str(find_Kth_smallest_number([1, 5, 12, 2, 11, 5], 3)))

  # since there are two 5s in the input array, our 3rd and 4th smallest numbers should be a '5'
  print("Kth smallest number is: " +
        str(find_Kth_smallest_number([1, 5, 12, 2, 11, 5], 4)))

  print("Kth smallest number is: " +
        str(find_Kth_smallest_number([5, 12, 11, -1, 12], 3)))


main()<jupyter_output>Kth smallest number is: 5
Kth smallest number is: 5
Kth smallest number is: 11
{'fraction_non_alphanumeric': 0.13313609467455623, 'fraction_numerical': 0.046227810650887574, 'mean_word_length': 4.075046904315197, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '36252', 'license': 'Apache-2.0', 'n_tokens_mistral': 1071, 'n_tokens_neox': 965, 'n_words': 362, 'path': '_notebooks/2022-04-17-Pattern-17.ipynb', 'repo_name': 'lxfz/blog', 'size': '2704'}