求无序列表中第K的大元素实例O(n)复杂度

求无序列表中第K的大元素实例O(n)复杂度-即刻学术

主要还是设立一个flag,列表中小于flag的组成左列表,大于等于flag的组成右列表,主要是不需要在对两侧列表在进行排序了,只需要生成左右列表就行,所以可以实现复杂度O(n)。

举个例子说明下步骤,比如有列表test_list=[6,5,4,3,2,1],找出第3大的元素,就是4

如果 flag=4:

l_list=[3,2,1]

r_list=[6,5]


因为第3大的元素,r_list长度为2,自然flag就是第3大的元素了,return flag,len(r_list)==k-1,就是结束递归的基线条件。

如果flag=1:

l_list=[]

r_list=[6,5,4,3,2]
问题就变成了求r_list里面第K大的元素了

如果flag=6:

l_list=[5,4,3,2,1]

r_list=[]
相当于求l_list里第k-(len(test_list)-len(r_list)+1)大的元素了,这里就是相当于求l_list=[5,4,3,2,1]第2大的元素

通过这三种情况进行递归,最终返回flag就是目标元素

最差复杂度就是n+n-1+n-2+n-3+……+1=(1+n)n/2,就是O(n²)

如果每次刚好二分,第一次取flag比较次数是n,第二次是n/2,依次下去是n/4,n/8…..n/2

就是n+n/2+n/4….复杂度自然就是O(n)了

golang 实现代码如下:


func findkMax(arr []int, k int) int{
	num := arr[0] // get first num
	arr = arr[1:]
	l_arr := make([]int,0)
	r_arr := make([]int,0)
	for _,val := range arr{
		if val < num {
			r_arr = append(r_arr, val)
		}else{
			l_arr = append(l_arr,val)
		}
	}
	r_len := len(r_arr)
	if r_len == k - 1{
		return num
	}else if r_len > k - 1 {
		return findkMax(r_arr,k)
	}else {
		former_r_len := len(r_arr) + 1  // 要找的部分在左边,就连通右边和取出来那个数一起减掉
		k = k - former_r_len
		return findkMax(l_arr,k)
	}

}

// test case
a:=[]int{4,1,3,2,16,9,10,14,8,7}
//maxaHeap(&a)
b := findkMax(a,3)
fmt.Println(b)  //3

给TA买糖
共{{data.count}}人
人已赞赏
后端/架构建站教程技术活软件工具

OneTypecho - Typecho多端小程序开源!by 即刻学术

2021-5-11 22:40:30

建站教程技术活

教你给网站添加个性化信息统计

2021-5-31 17:42:20

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索