作者 | 陌无崖
转载请联系授权
导语
今天分享的是数组中寻找k个最小数的解题思路,分别是全部排序和部分排序,一起来看看吧~
题目要求
有n个整数,请找出其中最小的k个数,要求时间复杂度尽可能的低。
解法一:利用全部排序
对于这种方法,我们只需要对我们的数组进行排序,然后取出前k个数就行了。那么对于全部排序,为了更加迅速我们使用快速排序的方法,因为快速排序的时间复杂度为O(nlogn),因此对于在n远大于k的情况下,此方法的时间复杂度为O(nlogn) + O(k) = O(nlogn),下面我们开始分析快速排序.
快速排序的思想
通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序列。
听起来有点晦涩难懂,简单来说就是对于一个数组,我们随便找一个数字,将这个数字和其它数字进行比较,比它大的放右边,比它小的放左边。然后就分成了两个数组,通过同样的方法将其余的两个数组进行找数字,排序,每个数组又得到两个数组,一直循环通过以上的方式,最终一定会出现只包含两个数字的数组,因为已经排好序,并且小的一直放在右边,大的一直在左边,规并之后就是一个排好序的数组。
如果还不太明白,可以看下面的一张图篇:
排序流程
(1)首先设定一个分界值,通过该分界值将数组分成左右两部分。
(2)将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于或等于分界值,而右边部分中各元素都大于或等于分界值。
(3)然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理
(4)重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后,整个数组的排序也就完成了。
代码分析
(1)首先需要定义一个基准数key
(2)为了保证比较的时候不超过或者不低于基准数的小标,需要定义指针p指向基准数,每次交换后,改变p
(3)为了遍历数组,我们也需要定义两个指针 i,j 指向首尾
完整排序代码
// 利用去全排序进行寻找最小的k个数
func FindNumBySort(data []int, k int) (result []int) {
if len(data) != 0 {
// 对数组进行快速排序
QuickSelect(data, 0, len(data)-1)
// 返回前k个数
return data[0:k]
}
return result
}
func QuickSelect(data []int, left, right int) {
// 指向基准数
p := left
// i,j分别代表了需要进行一趟排序的数组的首尾
i := left
j := right
// 定义我们的基准数,每次将数组的第一个值当作基准数比较
key := data[i]
for i <= j {
// 如果右边的数字大于基准数,不需要进行改变
for key <= data[j] && j >= p {
j--
}
if p <= j {
data[i], data[j] = data[j], data[i]
p = j
}
// 如果左边的数字小于基准数,不需要进行改变
for i <= p && key >= data[i] {
i++
}
if i <= p {
data[i], data[j] = data[j], data[i]
p = i
}
}
// 如果左边仍然有可排序的数组,继续递归
if p-left > 1 {
QuickSelect(data, left, p-1)
}
// 如果右边仍然有可排序的数组,继续递归
if right-p > 1 {
QuickSelect(data, p+1, right)
}
解法二:部分排序
对于题目的要求中,仔细分析其实我们没有必要对我们的数组进行排序,输出的k个数可以是无序的,因此我们只需要对部分元素进行排序,可以用如下的思路,我们可以选择前k个数默认为最小的k个数,存到数组temp中,然后求出temp数组中的最大值,用这个值去和其它的数比较,如果发现有比这个数小的,就进行交换,然后求出再次求出temp数组的最大值,按照这样的方式,我们仍然可以求出最小的k个数。求最大值我们可以根据选择排序或者交换排序求出最大值。时间复杂度为O(k),因为总共需要 比较遍历后面的n-k个数,因此时间复杂度是O(K) + (n-k)O(k) = O(nk)
选择排序的思想
第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。
选择排序代码分析
(1)首先我们可以默认第一个数为最小的数,让它去和后面的数进行比较,在比较的过程中,逐渐去寻找最小的数,记录下标
(2)找到最小的数后,我们就可以让该数和第一个数进行位置交换
(3)同样我们假设第二数是第二小的数,按照 上面的方式比较,求出第二个数字
(4)和第二个数进行交换
.....
选择排序求出最大值
有了上面的分析,我们很容易可以写出求出最大值的代码,就是遍历数组,不停的比较,因为,我们只需要求出最大值,因此我们不需要进行排序
// 利用部分排序寻找最小的k个数
func FindNumByPartSort(data []int, k int) (result []int) {
// 默认前k个数为最小
result = data[0:k]
for i := k; i < len(data); i++ {
// 找到最大值的坐标
max := select_sort(result)
// 比较
if result[max] > data[i] {
// 交换
result[max], data[i] = data[i], result[max]
}
}
return result
}
func select_sort(data []int) (max int) {
max = 0
for i := 1; i < len(data); i++ {
if data[i] > data[max] {
max = i
}
}
return max
}