当前位置: 首页 > 工具软件 > Quick[select] > 使用案例 >

QuickSelect 查找第 K 小的元素

费和惬
2023-12-01

Quick select 算法通常用来在未排序的数组中寻找第 k 小/第 k 大的元素。其方法类似于 Quick sort。

本质上是通过多次快速排序,当某次快速排序的枢纽元素恰好下标为 k-1 时,结束查找~

package main

import "fmt"

func core(nums []int, k, start, end int) int {
	left, right := start, end
	key := nums[left]

	for left < right {
		for left < right && nums[right] >= key {
			right --
		}
		nums[left] = nums[right]
		for left < right && nums[left] <= key {
			left ++
		}
		nums[right] = nums[left]
	}
	nums[left] = key //left 是下标,k 也是下标

	if left < k {
		return core(nums, k, left+1, end)
	} else if left > k {
		return core(nums, k, start, left-1)
	}
	return nums[left]
}

func findKSmallestNum(nums []int, k, start, end int) int {
	return core(nums, k-1, start, end)
}
func main() {
	nums := []int{1, 3, 2, 6, 5, 4}
	result := findKSmallestNum(nums, 3, 0, 5)
	fmt.Println(result)
}

  注意快速排序的写法,注意 k 和 left 均为下标 

 

 类似资料: