golang 中位数算法

题目：在给定数组中，找出第i小的数

package main

import "math/rand"

/*
 * 中位数算法
 */

func RandomSelect(A []int, p, r, i int) int {
	if p == r {
		return A[p]
	}

	q := RandPartition(A, p, r)
	k := q - p   1

	if k == i {
		return A[q]
	}

	if i < k {
		return RandomSelect(A, p, q-1, i)
	}

	return RandomSelect(A, q 1, r, i-k)
}

func RandPartition(A []int, p, r int) int {
	i := rand.Intn(r - p   1)
	A[p i], A[p] = A[p], A[p i]

	x := A[p]
	i = p

	for j := p   1; j <= r; j   {
		if A[j] <= x {
			i  
			A[i], A[j] = A[j], A[i]
		}
	}

	A[i], A[p] = A[p], A[i]

	return i
}

 

到此这篇关于“golang 中位数算法”的文章就介绍到这了,更多文章或继续浏览下面的相关文章，希望大家以后多多支持JQ教程网！

您可能感兴趣的文章：
golang 中位数算法
数据结构和算法(Golang实现)(10)基础知识-算法复杂度主方法
golang 位运算
Golang——运算符和格式化输出
golang的位运算操作符的使用
拓展学习-golang的基础语法和常用开发工具
golang 正负数取反
《Go语言四十二章经》第九章 运算符
Go语言学习 第五章 运算符和表达式 ②
go语言20小时从入门到精通（三、运算符）