经典算法:无序数组寻找第K大数值

ivansli 2021/11/18 329℃ 0

1. 寻找第K大数值

题意

有一个无序整数数组,请你根据排序思路,找出数组中第K大的数。
给定一个整数数组a, 请返回第K (1<=K<=n) 大的数(包括重复的元素,不用去重),保证答案存在。

示例
输入 [3,2,1,5,6,4] , 2
返回值 5

2. 常规思路

先对无序数组进行排序,然后对有序数组进行查找。

至于选择什么排序算法,有待确定。

先看一下,各种排序算法的复杂度以及稳定性。

看完上面比较之后,可能你心中已经有了自己的答案。

3. 解题思路

常规思路需要两大步:

  1. 先整体排序
  2. 在有序中查找目标值

那么,针对这道题,我们能不能在排序的过程中就确定目标值呢?

思考一下快排的二分特性

  1. 先找出一个数值的位置,该数值的左侧比自己小,右侧比自己大(整个数组一分为二)
  2. 再分别进行左、右两部分进行步骤1的操作,直至整个数组有序。

这里需要知道的是,在快排中某个数值左侧比自己小,右侧比自己大。该数值的位置就是在最终有序数组中的位置,也就是说可以在查找中确定目标位置。并且,在本题的处理过程中,平均情况下只处理1/2的数据量。

!!!

动图 - 快排算法

!!!

快排算法查找过程:

4. Go代码实现

func findKLargest(arr []int, k int) int {
    iflen(arr) == 0 || k > len(arr) {
        return-1
    }

    var find func(k int, l, r int) int
    find = func(k int, l, r int) int {
        /*
        // 对于正常的快排,需要下面的代码
        if l >= r {
            return
        }
        // 然而这里不需要,在寻找第k大的数据时 一般是 l==r
        */
        ll := l
        rr := r
        target := arr[l]

        // 倒序(第K大使用)排列 是 target >= arr[r]  / target <= arr[l]
        // 正序(第k小使用)排列 是 target <= arr[r]  / target >= arr[l]
        for l < r {
            for l < r && target >= arr[r] {
                r--
            }
            arr[l] = arr[r]

            for l < r && target <= arr[l] {
                l++
            }
            arr[r] = arr[l]
        }

        arr[l] = target
        // k在l的右侧
        // 为什么 下面无论是在左右侧,第一个参数都是k呢?
        // 因为,k指的是要找的数值的下标位置(第k大就是下标k-1)
        // 无论在左右侧,对于数组arr来说,其对应的下标都是固定的
        // 并且 l/r 每次都会变动,所以k这里是固定的
        if k > l {
            // 这里的  l+1, rr 也是数组的下标
            return find(k, l+1, rr)
        }elseif k < l {
            // k在l的左侧
            // 这里的  ll, l-1 也是数组的下标
            return find(k, ll, l-1)
        }

        // 此时目标自位置l处的target,就是第k个大的数值
        return target
    }

    // 第k大的数值,对应排序之后就是,数组下标k-1
    finds := find(k-1, 0, len(arr)-1)

    return finds
}

求第K大,则对数组排序排列。

求第K小,则对数组正序排列。

无论如何,都是从头开始找,这样处理更简单。

5. 算法题出处

牛客网- 寻找第K大:

https://www.nowcoder.com/practice/e016ad9b7f0b45048c58a9f27ba618bf

评论啦~