剑指 Offer 40. 最小的k个数

题目

剑指 Offer 40. 最小的k个数

题意就是从一个整数数组中，取出前k个最小的数。

题解

简单直接

//Go
import "sort"
func getLeastNumbers(arr []int, k int) []int {
    sort.Ints(arr)  // 按从小到大排序
    return arr[:k]  // 从下表0开始算，取前k个最小值后返回
}

自定义排序

import "sort"

type IntSlice []int

func (s IntSlice) Len() int { return len(s) }

func (s IntSlice) Swap(i, j int){ s[i], s[j] = s[j], s[i] }

func (s IntSlice) Less(i, j int) bool { return s[i] < s[j] }

func getLeastNumbers(arr []int, k int) []int {
    sort.Sort(IntSlice(arr))
    return arr[:k]
}

快速排序

// Go
func getLeastNumbers(arr []int, k int) []int {
	if k == 0 || len(arr) == 0 {
		return []int{0}
	}

	return quickSort(arr, 0, len(arr)-1, k-1)
}

// 函数传入待排序数组 nums
// 排序区间的左端点 left
// 排序区间的右端点 right
func quickSort(nums []int, left, right, index int) []int {
	// 调用函数 partition，将 left 和 right 之间的元素划分为左右两部分
	mid := partition(nums, left, right)
	// 如果 mid 下标恰巧为 index，那么找到了最小的 k 个数
	if mid == index {
        return nums[:mid+1]
	} else if mid > index {
		// 对 mid 左侧的元素进行快速排序
		return quickSort(nums, left, mid-1, index)
	} else {
		// 对 mid 右侧的元素进行快速排序
		return quickSort(nums, mid+1, right, index)
	}

	return nil
}

func partition(nums []int, left, right int) int {
	// 设置当前区间的第一个元素为基准元素
	pivot := nums[left]
	// left 向右移动，right 向左移动，直到 left 和 right 指向同一元素为止
	for left < right {
		// 只有当遇到小于 pivot 的元素时，right 才停止移动
		// 此时，right 指向了一个小于 pivot 的元素，这个元素不在它该在的位置上
		for left < right && nums[right] >= pivot {
			// 如果 right 指向的元素是大于 pivot 的，那么
			// right 不断的向左移动
			right--
		}
		// 将此时的 nums[left] 赋值为 nums[right]
		// 执行完这个操作，比 pivot 小的这个元素被移动到了左侧
		nums[left] = nums[right]

		// 只有当遇到大于 pivot left 才停止移动
		// 此时，left 指向了一个大于 pivot 的元素，这个元素不在它该在的位置上
		for left < right && nums[left] <= pivot {
			// 如果 left 指向的元素是小于 pivot 的，那么
			// left 不断的向右移动
			left++
		}

		// 将此时的 nums[right] 赋值为 nums[left]
		// 执行完这个操作，比 pivot 大的这个元素被移动到了右侧
		nums[right] = nums[left]
	}
	// 此时，left 和 right 相遇，那么需要将此时的元素设置为 pivot
	// 这个时候，pivot 的左侧元素都小于它，右侧元素都大于它
	nums[left] = pivot

	return left
}

参考资料

剑指 Offer 40. 最小的 k 个数（基于快速排序的数组划分，清晰图解)