My-Notes

Search

SearchSearch

006.随机选择算法

Dec 14, 2023, 7 min read

前置知识：随机快速排序

快速选择算法

快速选择算法基于快排的思想衍生，其可以使某些需要  时间复杂度的问题，在平均复杂度  下完成。

题目

数组中的第 K 个最大（小）元素

题目描述

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题

测试链接

215.数组中的第K个最大元素

答案

注意：快速选择算法会修改原数组

var (
	N   int
	K   int
	arr []int
)
 
func findKthLargest(nums []int, k int) int {
	N = len(nums)
	K = k
	arr = nums
	return quickSelection(0, N-1)
}
 
func quickSelection(left, right int) int {
	x := arr[left+rand.Intn(right-left+1)]
	l, r := left, right
	for i := left; i <= r; {
		if arr[i] < x {
			arr[l], arr[i] = arr[i], arr[l]
			l++
			i++
		} else if arr[i] > x {
			arr[r], arr[i] = arr[i], arr[r]
			r--
		} else {
			i++
		}
	}
	if K < N-r {
		return quickSelection(r+1, right)
	}
	if K > N-l {
		return quickSelection(left, l-1)
	}
	return x
}
  • 时间复杂度：O(n)，证明过程可以参考「《算法导论》9.2：期望为线性的选择算法」
    • 最差情况：
    • 最好情况：
    • 期望：
  • 空间复杂度：O(log⁡n)，递归使用栈空间的空间代价的期望为 O(log⁡n)

很容易可以改成非递归，空间复杂度降为 O(1)：

func findKthLargest(arr []int, k int) int {
	n := len(arr)
	for left, right := 0, n-1; left <= right; {
		x := arr[left+rand.Intn(right-left+1)]
		l, r := left, right
		for i := left; i <= r; {
			if arr[i] < x {
				arr[l], arr[i] = arr[i], arr[l]
				l++
				i++
			} else if arr[i] > x {
				arr[r], arr[i] = arr[i], arr[r]
				r--
			} else {
				i++
			}
		}
		if k < n-r {
			left = r + 1
		} else if k > n-l {
			right = l - 1
		} else {
			return x
		}
	}
 
	panic("no answer")
}

该题还可以 使用堆来解决

摆动排序

题目描述

给你一个整数数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序

你可以假设所有输入数组都可以得到满足题目要求的结果

进阶：你能用 O(n) 时间复杂度和 / 或原地 O(1) 额外空间来实现吗？

测试链接

324.摆动排序 II

思路

首先考虑数组有序的情况如何解决问题，如果数组已经有序 (降序) 则可以将数组分为两半 [left, right]，令左边的数都按顺序放在奇数位，右边的数按顺序放在偶数位即可

当然，如果直接排序，时间复杂度为 O(nlogn)。其实不需要使整个数组有序，只要得到一个中位数 median，使得数组可以分为三部分：[>median, =median, <median] 即可（题目保证了输入数组满足要求）

为什么要降序？降序保证左右 =median 的部分分布到两侧，如下：

[>median, =median, <median] -> [>median, L=median] 和 [R=median, <median]

奇          >median          L=median
偶 R=median          <median

使用快速选择算法在 O(n) 内找到中位数（上面 数组中的第 K 个最大元素 的思路），将数组划分为 [>median, =median, <median] 的形式，然后使用三路合并的方法原地修改数组，使其符合题意

答案

var (
	n   int
	arr []int
)
 
func wiggleSort(nums []int) {
	n = len(nums)
	if n == 0 {
		return
	}
	arr = nums
	// 中位数
	median := findKthLargest((n + 1) >> 1)
	threeWayPartition(median)
}
 
// 获取第 k 大的数值 x
// 并将数组划分为 [>x, =x, <x] 的形式
func findKthLargest(k int) int {
	for left, right := 0, n-1; left <= right; {
		l, r := left, right
		// 力扣 go 版本是最新版本，使用 globalRand
		x := arr[rand.Intn(right-left+1)+left]
		for i := l; i <= r; {
			if arr[i] > x {
				arr[l], arr[i] = arr[i], arr[l]
				l++
				i++
			} else if arr[i] < x {
				arr[r], arr[i] = arr[i], arr[r]
				r--
			} else {
				i++
			}
		}
		if k < n-r {
			left = r + 1
		} else if k > n-l {
			right = l - 1
		} else {
			return x
		}
	}
 
	panic("no answer")
}
 
// 三路合并、三路切分
func threeWayPartition(median int) {
	left, right := 0, n-1
	for i := 0; i <= right; {
		ii, li, ri := getIdx(i), getIdx(left), getIdx(right)
		if arr[ii] > median {
			arr[ii], arr[li] = arr[li], arr[ii]
			left++
			i++
		} else if arr[ii] < median {
			arr[ii], arr[ri] = arr[ri], arr[ii]
			right--
		} else {
			i++
		}
	}
}
 
func getIdx(idx int) int {
	// (n | 1)：奇数 - 1；偶数不变
	return (idx<<1 + 1) % (n | 1)
}

备注

期望复杂度不会算？不明白为啥？

不要慌！

随机快速排序、随机选择算法，时间复杂度的证明理解起来很困难，只需记住结论，但并不会对后续的算法学习造成什么影响

因为数学很好才能理解的算法和数据结构其实比较少，绝大部分的内容都只需要高中数学的基础就能理解

算法导论第 9 章，还有一个 BFPRT 算法，不用随机选择一个数的方式，也能做到时间复杂度 O(n)，额外空间复杂度 O(logn)

早些年我（左神）还讲这个算法，不过真的很冷门，很少在笔试、面试、比赛场合出现，所以算了。有兴趣的同学可以研究一下

Graph View

Backlinks