剑指Offer 最小的K个数

骑猪看日落 2022-06-10 12:14 211阅读 0赞

题目描述:

输入n个整数，找出其中最小的k个数

思路:

首先想到的是对数组进行按从小到大排序然后再选出最小的前K个数。排序算法里选择排序是每次排序都可以确定数组在最后排好序数组的位置。

1.  首先想到的是最简单的选择排序，由于只需要选出前K个最小的，因此只需要排序K趟即可

public static int[] getLeastNumberBySelectSort(int[] array, int n) {
            if (array == null || array.length == 0 || n < 0 || n > array.length) {
                return null;
            }
            int index = 0;
            int min;
            for (int i = 0; i < n; i++) {
                min = array[i + 1];
                for (int j = i + 1; j < array.length; j++) {
                    if (array[j] < min) {
                        min = array[j];
                        index = j;
                    }
                }
                if (min < array[i]) {
                    int temp = array[i];
                    array[i] = array[index];
                    array[index] = temp;
                }
            }
            return Arrays.copyOf(array, n);
        }

2.同样属于选择排序的堆排序

public static int[] getLeastNumberByHeapSort(int[] array, int n) {
            if (array == null || array.length == 0 || n < 0 || n > array.length) {
                return null;
            }
            initMaxHeap(array);
            int temp;
            //只需调整n次即可
            for (int i = array.length - 1; i >= array.length - n; i--) {
                temp = array[0];
                array[0] = array[i];
                array[i] = temp;
                createMaxHeap(array, i, 0);
            }
            return Arrays.copyOf(array, n);
        }
    
        /** * 初始化最大堆 * * @param array */
        private static void initMaxHeap(int[] array) {
            for (int i = (array.length - 1) / 2; i >= 0; i--) {
                createMaxHeap(array, array.length, i);
            }
        }
    
        /** * 调整为最大堆 */
        private static void createMaxHeap(int[] array, int length, int index) {
            int rootIndex = index;
            int childIndex = 2 * index + 1;
    
            int temp = array[rootIndex];
            boolean flag = true;
    
            while (childIndex < length && flag) {
                if (childIndex < length - 1 && array[childIndex] < array[childIndex + 1]) {
                    childIndex++;
                }
                if (temp >= array[childIndex]) {
                    flag = false;
                } else {
                    array[rootIndex] = array[childIndex];
                    rootIndex = childIndex;
                    childIndex = 2 * rootIndex + 1;
                }
            }
            array[rootIndex] = temp;
        }

3 .使用快排实现 这里采用的是双指针快排，取首元素为基准元素，从前往后扫描比基准元素大的元素，从后往左扫描比基准元素小的元素，这样一趟排序下来可以确定该基准元素的最终位置index

*  当index小于K时 需要对基准元素之后的元素再进行快排
 *  index大于K时 证明最小的K的元素排在基准元素前面 因此对之前的元素再进行快排
 *  index等于K时 证明从基准元素前截止到基准元素的数据就是需要找到最小的K个元素

public static int[] getLeastNumberByQuickSort(int[] array, int n) {
            if (array == null || array.length == 0 || n < 0 || n > array.length) {
                return null;
            }
            int start = 0;
            int end = array.length - 1;
            int result = partition(array, start, end);
            while (result != n - 1) {
                if (result > n - 1) {
                    end = result - 1;
                    result = partition(array, start, end);
                } else {
                    start = result + 1;
                    result = partition(array, start, end);
                }
            }
            return Arrays.copyOf(array, n);
        }
    
        private static int partition(int[] array, int start, int end) {
            if (start >= end) {
                return -1;
            }
            int base = array[start];
            int leftIndex = start;
            int rightIndex = end;
            while (leftIndex != rightIndex) {
                while (leftIndex < rightIndex && array[rightIndex] >= base) {
                    rightIndex--;
                }
                while (leftIndex < rightIndex && array[leftIndex] <= base) {
                    leftIndex++;
                }
                if (leftIndex < rightIndex) {
                    int temp = array[leftIndex];
                    array[leftIndex] = array[rightIndex];
                    array[rightIndex] = temp;
                }
            }
    
            array[start] = array[leftIndex];
            array[leftIndex] = base;
    
            return leftIndex;
        }

编写测试用例

@RunWith(Parameterized.class)
    public class GetLeastNumberTest extends BaseTest { 
    
        @Parameterized.Parameters
        public static List<Object[]> data() {
            List<Object[]> data = new ArrayList<>();
            //1.正常情况
            data.add(new Object[]{
       new int[]{
       4, 5, 1, 6, 2, 7, 3, 8}, 4, new int[]{
       1, 2, 3, 4}});
            //2.元素都相等情况
            data.add(new Object[]{
       new int[]{
       1, 1, 1, 1, 1, 1, 1}, 4, new int[]{
       1, 1, 1, 1}});
            //3.数组为空
            data.add(new Object[]{
       null, 4, null});
            //4.个数n非法
            data.add(new Object[]{
       new int[]{
       1, 1, 1, 1, 1, 1, 1}, -1, null});
            data.add(new Object[]{
       new int[]{
       1, 1, 1, 1, 1, 1, 1}, 100, null});
            return data;
        }
    
        private int[] array;
        private int n;
        private int[] result;
    
        public GetLeastNumberTest(int[] array, int n, int[] result) {
            this.array = array;
            this.n = n;
            this.result = result;
        }
    
        @Test
        public void testFindBySelectSort() throws Exception {
            int[] leastNumber = GetLeastNumber.getLeastNumberBySelectSort(array, n);
            assertArrayEquals(result, leastNumber);
        }
    
        @Test
        public void testFindByQuickSort() throws Exception {
            int[] leastNumber = GetLeastNumber.getLeastNumberByQuickSort(array, n);
            //注意:快排顺序可能不会按照递增要求 第一个测试样例输出的是[2, 3, 1, 4]
            LOGGER.info(Arrays.toString(leastNumber));
        }
    
        @Test
        public void testFindByHeapSort() throws Exception {
            int[] leastNumber = GetLeastNumber.getLeastNumberByHeapSort(array, n);
            LOGGER.info(Arrays.toString(leastNumber));
        }
    }

--------------------