【面试题30】最小的k个数

【题目描述】

输入n个整数，找出其中最小的k个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。

【解决方案】

测试用例：

1. 功能测试（输入数组中有相同的数字，输入数组中没有相同的数字）；

2. 边界值测试（输入的k等于1或者等于数组的长度）；

3. 特殊情况测试（k小于1，k大于数组的长度，指向数组的指针为null）；

解法一：基于Partition函数来解决

优点：时间复杂度为o(n)；

缺点：会修改原数组；不适用于数据量较大的查找（例如，数组一次性加载不到内存中）；

我的代码实现，仅供参考：

        public static void GetLeastNums(int[] arr, int k)
        {
            if (arr == null || arr.Length < k || k <= 0)
                return;

            int start = 0;
            int end = arr.Length - 1;
            int index = Partition(arr, start, end);

            while (k - 1 != index)
            {
                if (index > k - 1)
                {
                    end = index - 1;
                    index = Partition(arr, start, end);
                }
                else
                {
                    start = index + 1;
                    index = Partition(arr, start, end);
                }
            }

            for (int i = 0; i < k; i++)
            {
                Console.Write(arr[i]);
            }
        }

        public static int Partition(int[] arr, int start, int end)
        {
            int temp = arr[start];

            while (start < end)
            {
                while (start < end && arr[end] >= temp)
                    end--;
                arr[start] = arr[end];

                while (start < end && arr[start] <= temp)
                    start++;
                arr[end] = arr[start];
            }

            arr[start] = temp;

            return start;
        }

解法二：利用大根堆的特性，在堆中保存前k个小的数，遍历数组，满足则替换

优点：不需要修改原数组；适合数据量大，所求k较小的情况；

缺点：时间复杂度为O(nlogk)；

我的代码实现，仅供参考：

        public static void GetLeastNums(int[] arr, int k)
        {
            if (arr == null || arr.Length < k || k <= 0)
                return;

            int[] arrK = new int[k];

            //为大根堆数组赋值
            for (int i = 0; i < k; i++)
            {
                arrK[i] = arr[i];
            }

            //构建大根堆
            for (int j = arrK.Length / 2 - 1; j >= 0; j--)
            {
                MaxHeapify(arrK, j);
            }

            for (int i = k; i < arr.Length; i++)
            {
                //如果比大根堆的最大值还要大，则覆盖最大值，然后调整大根堆
                if (arrK[0] > arr[i])
                {
                    arrK[0] = arr[i];
                    MaxHeapify(arrK, 0);
                }
            }

            foreach (int num in arrK)
                Console.Write(num);
        }

        /// <summary>
        /// 调整大根堆
        /// </summary>
        /// <param name="arr"></param>
        public static void MaxHeapify(int[] arr, int currentIndex)
        {
            int left = currentIndex * 2 + 1;
            int right = currentIndex * 2 + 2;
            int large = currentIndex;

            if (left < arr.Length && arr[left] > arr[large])
            {
                large = left;
            }

            if (right < arr.Length && arr[right] > arr[large])
            {
                large = right;
            }

            if (large != currentIndex)
            {
                Swap(arr, large, currentIndex);

                MaxHeapify(arr, large);
            }
        }

        public static void Swap(int[] arr, int indexA, int indexB)
        {
            int temp = arr[indexA];
            arr[indexA] = arr[indexB];
            arr[indexB] = temp;
        }