最小的k个数

描述：
输入n个整数，找出其中最小的k个数。

例子：
例如输入4 、5 、1、6、2、7、3 、8 这8 个数字，则最小的4 个数字是1 、2、3
、4

解题思路：
解法一：O(n)时间算法，只有可以修改输入数组时可用。
可以基于Partition函数来解决这个问题。如果基于数组的第k个数字来调整，使得比
第k个数字小的所有数字都位于数组的左边，比第k个数字大的所有数字都位于数组
的右边。这样调整之后，位于数组中左边的k个数字就是最小的k 个数字（这k 个数
字不一定是排序的〉。
解法二： O（nlogk）的算法，精剧适合处理海量数据。
先创建一个大小为k的数据容器来存储最小的k个数字，接下来我们每次从输入的n
个整数中读入一个数．如果容器中已有的数字少于k个，则直接把这次读入的整数
放入容器之中：如果容器中己有k 数字了，也就是容器己满，此时我们不能再插入
新的数字而只能替换已有的数字。找出这己有的k 个数中的最大值，然后1在这次待
插入的整数和最大值进行比较。如果待插入的值比当前己有的最大值小，则用这个
数替换当前已有的最大值：如果待插入的值比当前已有的最大值还要大，那么这个
数不可能是最小的k个整数之一，于是我们可以抛弃这个整数。
因此当容器满了之后，我们要做3 件事情： 一是在k 个整数中找到最大数： 二是有
可能在这个容器中删除最大数： 三是有可能要插入一个新的数字。我们可以使用一
个大顶堆在O(logk）时间内实现这三步操作。

    // 解法一
    fun getK_LeastNumber(inputArr: IntArray, outputArr:IntArray){
        if (inputArr.isEmpty() || outputArr.isEmpty() || inputArr.size < outputArr.size) {
            throw IllegalArgumentException("invalid input")
        }

        var mStart = 0
        var mEnd = inputArr.size -1
        var index = partition(inputArr, mStart, mEnd)
        var target = outputArr.size - 1
        while (index != target) {
            if (index > target) {
                mEnd = index-1
            } else {
                mStart = index + 1
            }
            index = partition(inputArr , mStart ,mEnd)
        }

        System.arraycopy(inputArr,0,outputArr,0, outputArr.size)
    }

   fun partition(arr: IntArray, start:Int, end:Int):Int {
        val tmp = arr[start]
        var mEndIndex = end
        var mStartIndex = start
        while (mStartIndex < mEndIndex) {
            while (mStartIndex < mEndIndex && arr[mEndIndex] >= tmp) {
                mEndIndex --
            }
            arr[mStartIndex] = arr[mEndIndex]

            while (mStartIndex < mEndIndex && arr[mStartIndex] <= tmp) {
                mStartIndex ++
            }
            arr[mEndIndex] = arr[mStartIndex]
        }
        arr[mStartIndex] = tmp
        return mStartIndex
    }