首页 > 代码库 > 【算法】数组与矩阵问题——找到无序数组中最小的k个数
【算法】数组与矩阵问题——找到无序数组中最小的k个数
1 /** 2 * 找到无序数组中最小的k个数 时间复杂度O(Nlogk) 3 * 过程: 4 * 1.一直维护一个有k个数的大根堆,这个堆代表目前选出来的k个最小的数 5 * 在堆里的k个元素中堆顶的元素是最小的k个数中最大的那个。 6 * 2.接下来,遍历整个数组,遍历过程中看当前数是否比堆顶元素小: 7 * 如果是,就把堆顶元素替换成当前的数,然后从堆顶的位置调整整个堆,让替 8 * 换操作后堆的最大元素继续处在堆顶的位置; 9 * 如果不是,则不进行任何操作,继续遍历下一个数; 10 * 3.在遍历完成后,堆中的k个数就是所有数组中最小的k个数 11 */ 12 public class getMinKNumsByHeap { 13 14 public int[] getMinKNumsByHeap(int[] arr, int k) { 15 if (k < 1 || k > arr.length) { 16 return arr; 17 } 18 int[] kHeap = new int[k]; 19 for (int i = 0; i < k; i++) { 20 heapInsert(kHeap, arr[i], i); 21 } 22 for (int i = k; i != arr.length; i++) { 23 if (arr[i] < kHeap[0]) { 24 kHeap[0] = arr[i]; 25 heapify(kHeap, 0, k); 26 } 27 } 28 return kHeap; 29 } 30 31 // 建堆的过程 32 private void heapInsert(int[] arr, int value, int index) { 33 34 arr[index] = value; 35 while (index != 0) { 36 int parent = (index - 1) / 2; 37 if (arr[parent] < arr[index]) { 38 swap(arr, parent, index); 39 index = parent; 40 } else { 41 break; 42 } 43 } 44 } 45 46 // 调整堆的过程 47 private void heapify(int[] arr, int index, int heapSize) { 48 49 int left = index * 2 + 1; 50 int right = index * 2 + 2; 51 int largest = index; 52 while (left < heapSize) { 53 if (arr[left] > arr[index]) { 54 largest = left; 55 } 56 if (right < heapSize && arr[right] > arr[largest]) { 57 largest = right; 58 } 59 if (largest != index) { 60 swap(arr, largest, index); 61 } else { 62 break; 63 } 64 index = largest; 65 left = index * 2 + 1; 66 right = index * 2 + 2; 67 } 68 } 69 70 // 交换 71 public void swap(int[] arr, int index1, int index2) { 72 int tmp = arr[index1]; 73 arr[index1] = arr[index2]; 74 arr[index2] = tmp; 75 } 76 }
【算法】数组与矩阵问题——找到无序数组中最小的k个数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。