剑指offer-29、最⼩的k个数
<h2 id="题描述">题⽬描述</h2><p>输⼊ n 个整数，找出其中最⼩的 K 个数。例如输⼊ 4,5,1,6,2,7,3,8 这 8 个数字，则最⼩的 4 个数字是 1,2,3,4 。</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="排序法">排序法</h3>
<p>最直接的思路是将数组排序后取前k个元素</p>
<pre><code class="language-java">public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
ArrayList<Integer> result = new ArrayList<>();
if (input == null || k <= 0 || k > input.length) {
return result; // 处理非法输入
}
Arrays.sort(input); // 使用Java内置排序，时间复杂度O(n log n)
for (int i = 0; i < k; i++) {
result.add(input); // 取前k个元素
}
return result;
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：主要由 <code>Arrays.sort()</code> 决定，为 O(n log n)</li>
<li><strong>空间复杂度</strong>：O(k)，用于存储结果的列表</li>
</ul>
<h3 id="大顶堆法推荐">大顶堆法（推荐）</h3>
<p>维护一个大小为k的<strong>大顶堆</strong>（Max-Heap），堆顶是当前k个数中的最大值。遍历数组，如果当前数比堆顶小，则替换堆顶并调整堆</p>
<p>这⾥不展开最⼤堆和最⼩堆的具体讲解，什么是最⼤堆/最⼩堆呢？</p>
<ul>
<li>⼤/⼩堆树是完全⼆叉树</li>
<li>⼤/⼩堆树的每⼀个节点不⼩于/不⼤于其孩⼦节点。</li>
</ul>
<pre><code class="language-java">public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
ArrayList<Integer> result = new ArrayList<>();
if (input == null || k <= 0 || k > input.length) {
return result;
}
// 创建一个大顶堆，使用自定义比较器实现降序排列
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
for (int num : input) {
if (maxHeap.size() < k) {
maxHeap.offer(num); // 堆未满，直接加入
} else if (num < maxHeap.peek()) { // 当前数比堆顶最大值小
maxHeap.poll(); // 移除堆顶最大值
maxHeap.offer(num); // 将当前数加入堆
}
}
result.addAll(maxHeap);
return result;
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n log k)。每次插入或删除堆的操作需要 O(log k) 时间，共需进行 n 次这样的操作</li>
<li><strong>空间复杂度</strong>：O(k)，堆的大小</li>
</ul>
<p>堆这种数据结构适合处理<strong>海量数据</strong>（数据无法一次性装入内存），或者当 <strong>k 远小于 n</strong> 时非常高效。</p>
<p><strong>大数据问题处理面试题</strong>：https://www.seven97.top/interview/intelligence-massivedata/massivedataprocessing.html</p>
<h3 id="快速选择法效率最优">快速选择法（效率最优）</h3>
<p>基于快速排序的 <strong>partition</strong> 操作。每次随机选择一个基准元素（pivot），将数组划分为比基准小和比基准大的两部分。根据基准的位置与k的关系，决定继续划分哪一部分</p>
<pre><code class="language-java">public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
ArrayList<Integer> result = new ArrayList<>();
if (input == null || k <= 0 || k > input.length) {
return result;
}
quickSelect(input, 0, input.length - 1, k);
for (int i = 0; i < k; i++) {
result.add(input);
}
return result;
}
private void quickSelect(int[] arr, int left, int right, int k) {
if (left >= right) return;
int pivotIndex = partition(arr, left, right);
if (pivotIndex == k - 1) { // 基准点正好是第k-1个位置（0-indexed），则其左边就是最小的k个数
return;
} else if (pivotIndex > k - 1) { // 基准点位置大于k-1，说明最小的k个数在左边
quickSelect(arr, left, pivotIndex - 1, k);
} else { // 基准点位置小于k-1，说明最小的k个数还需要包括右边的一部分
quickSelect(arr, pivotIndex + 1, right, k);
}
}
// 分区操作，将小于基准的数放在左边，大于基准的数放在右边，返回基准的最终位置
private int partition(int[] arr, int left, int right) {
// 随机选择基准，避免最坏情况
int randomIndex = new Random().nextInt(right - left + 1) + left;
swap(arr, left, randomIndex);
int pivot = arr;
int i = left, j = right;
while (i < j) {
while (i < j && arr >= pivot) j--;
while (i < j && arr <= pivot) i++;
if (i < j) swap(arr, i, j);
}
swap(arr, left, i);
return i;
}
private void swap(int[] arr, int i, int j) {
int temp = arr;
arr = arr;
arr = temp;
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：<strong>平均 O(n)</strong>。每次partition操作平均处理n个元素，但每次都能将问题规模大致减半（n + n/2 + n/4 + ... ≈ 2n）。最坏情况（每次选的基准都是最大或最小值）下为O(n²)，但随机选择基准有效避免了最坏情况的发生。</li>
<li><strong>空间复杂度</strong>：O(log n)，递归调用栈的深度</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19076709
頁:
[1]