求无序列表中第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