本文共 5418 字,大约阅读时间需要 18 分钟。
题目描述:
输入n个整数,找出其中最小的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
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
转载地址:http://whqli.baihongyu.com/