【leetcode】Quick select

Introduction

Quick select is a transformation of quicksort, we can use it to find the $k-th$ element in a list if it exists. The average time complexity of this algorithm is $O(n)$. We all know that the average time complexity of quick sort is $O(nlogn)$.

This kind of problem can also be solved by using Max_heap or Min_heap, the time complexity is $O(nlogk)$.

Quick Select

Input: array nums, int k. (find k-th smallest element in an unsorted array)
Output: int target

1. Choose an element from the array as pivot, exchange the position of pivot and number at the end of the array.
   • The pivot can either be the end element or a random chosen element. A random chosen pivot can make the algorithm much possibly run in average case time.
2. Partition the array into 2 parts in which the numbers in left subarray is less than (or equal to) the pivot and the numbers in right subarray is greater than (or equal to) the pivot.
3. Exchange pivot (at the end of the array now) with the first element in the right part.
4. Compare k with length of the left subarray, say, len.
   • if k == len + 1， then pivot is the target.
   • if k <= len, repeat from step 1 on the left subarray.
   • if k > len, k = k - len, repeat from step 1 on the right subarray.

implementation

#快速选择 找到第（k+1）小的数
def quickselect(nums, left, right, k):
    if left > right:
        return
    #随机选取哨兵,可以一定程度上降低时间复杂度
    random_index = random.randint(left, right)
    nums[left], nums[random_index] = nums[random_index], nums[left]
    pivot = nums[left]
    # 快速选择模板 为了找到哨兵pivot 在数组中的位置
    i , j = left + 1, right
    while i <= j:
        while i <= j and nums[i] <= pivot: i += 1
        while i <= j and nums[j] > pivot: j -= 1
        if i <= j:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
            j -= 1
    nums[left], nums[j] = nums[j], nums[left]
    # j 为 pivot 在数组中的位置索引
    if j == k:
        return nums[j]
    elif j < k:
        return quickselect(nums, j+1, right, k)
    else:
        return quickselect(nums, left, j-1, k)

Quick Sort

def quicksort(nums, left, right):
    if left > right:
        return
    pivot = nums[left]
    i, j = left+1, right
    while i <= j:
        while i <= j and nums[i] <= pivot: i += 1
        while i <= j and nums[j] >= pivot: j -= 1
        if i <= j:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
            j -= 1
    nums[left], nums[j] = nums[j], nums[left]
    #与快速选择的主要区别在于：快速排序需要再对两边同时递归，从而对整个数组进行排序。而快速选择只需要判断k的位置然后选择一边进行递归，类似于二分查找的操作，它只想找到第k个元素而不关系其他元素在数组中怎么排列，从而降低了时间复杂度
    quicksort(nums, left, j-1)
    quicksort(nums, j+1, right)

Leetcode examples:

• Kth Largest Element in an Array
• Top K Frequent Elements