关于最小k个数的问题
下面是我的代码：
func smallestK(arr []int, k int) []int {
if len(arr)==0||k==0{
return make([]int,0)
}
return smallestK2(arr,0,len(arr)-1,k)
}
func smallestK2(arr []int,l int,r int ,k int) []int {
// //解题思想：三路快排
if l >= r {
return make([]int,0)
}
p :=partition(arr,l,r)
if p-1 == k{
return arr[0:p-1]
}else if p-1 < k{
return smallestK2(arr,p+1,r,k)
}else {
return smallestK2(arr,l,p-1,k)
}
}
func partition(arr []int,l int ,r int)int{
var p int = rand.Intn(r-l+1) + l
arr[l], arr[p] = arr[p], arr[l]
//arr[l+1...i-1]<=v;arr[j+1...r]>=v
i := l + 1
j := r
for {
for i <= j && arr[i] < arr[l] {
i++
}
for j >= i && arr[j] > arr[l] {
j--
}
if i >= j {
break
}
arr[i], arr[j] = arr[j], arr[i]
i++
j--
}
arr[l], arr[j] = arr[j], arr[l]
return j
}实在是看不出来我那个地方有问题，在leetcode中运行截图如下：
输出一直显示为空，这个测试数据貌似也并不符合我设置为空的情况，然后我尝试将这个测试案例复制到我本机环境中尝试，结果发现运行没有问题：
是我那个点没有注意到吗，如果是代码有问题的话，为什么在本地可以呢？希望bobo老师解答一下谢谢?
11
收起
正在回答
1回答
题号是？？？
==========
我修改成如下可以通过：
func smallestK(arr []int, k int) []int {
if len(arr)==0||k==0{
return make([]int,0)
}
return smallestK2(arr,0,len(arr)-1,k - 1)
}
func smallestK2(arr []int,l int,r int ,k int) []int {
// //解题思想：三路快排
if l >= r {
// 核心问题在这里
return arr[0:l+1]
}
p :=partition(arr,l,r)
if p == k{
return arr[0:p+1]
}else if p < k{
return smallestK2(arr,p+1,r,k)
}else {
return smallestK2(arr,l,p-1,k)
}
}
func partition(arr []int,l int ,r int)int{
var p int = rand.Intn(r-l+1) + l
arr[l], arr[p] = arr[p], arr[l]
//arr[l+1...i-1]<=v;arr[j+1...r]>=v
i := l + 1
j := r
for {
for i <= j && arr[i] < arr[l] {
i++
}
for j >= i && arr[j] > arr[l] {
j--
}
if i >= j {
break
}
arr[i], arr[j] = arr[j], arr[i]
i++
j--
}
arr[l], arr[j] = arr[j], arr[l]
return j
}核心是 l >= r 的时候不是没有找到。因为 l == r 依然是一个合法的搜索空间，此时的 l 和 r 应该就是要找的索引 k - 1.
P.S. 因为我不习惯传入的 k 不是索引，所以代码中我把 k 的偏移在初始的时候处理了，初始传入的是 k - 1（和课程中的逻辑一样）。这一点你可已根据你的逻辑再调整。
继续加油！：）
相似问题
登录后可查看更多问答，登录/注册
恭喜解决一个难题，获得1积分~
来为老师/同学的回答评分吧
0 星