查找最小的k个元素
题目：输入n个整数，输出其中最小的k个。
例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。
我的思路：利用二叉堆，构建一个容量为k的定长最小二叉堆，遍历数组，逐个将元素add进堆，完毕返回堆中所有元素即为最小的k个元素
package org.jf.alg;
/**
* 定长小根堆
* 数组存储，数组第一个元素留空
*
* 第k个元素的左儿子为 a[2k],右儿子为a[2k+1]
*
* 第k个元素的父节点为a[k/2]
*
* k从1记起
*
* @author chenjf
*
*
*/
public class LittleHeadFixedBinHeap<T extends Comparable>
{
private Object array[];
private int current_size = 0;
/**
*
* @param size 堆大小
*/
public LittleHeadFixedBinHeap(int size)
{
array = new Object[size+1];
}
public LittleHeadFixedBinHeap(int size,T []data_array)
{
array = new Object[size+1];
for(int i=0;i<data_array.length;i++)
{
this.add(data_array[i]);
}
}
/**
* 往堆中添加一个元素
*
*分两种情况：
*1.当前堆未满，直接添加到末尾，回溯保持堆性质
*2.当前堆已满，则找出最后一层中最大元素并与当前元素比较，若当前元素小，则替换，否则什么也不做
*
* @param data
*/
public void add(T data)
{
int comp_begin = current_size/2+1;//求最大值的起始位置
int indx = 1;//记录当前新插入的元素索引
if(current_size<array.length-1)//堆未满 直接将新元素插入末尾
{
array[++current_size]=data;
indx = current_size;
}
else//堆已满 查找最后一层中的最大值
{
int max_indx = comp_begin;
T max = (T) array[max_indx];
int i=comp_begin;
while(i<array.length)
{
if(max.compareTo((T)array[i])<0)
{
max_indx = i;
max = (T) array[max_indx];
}
i++;
}
if(max.compareTo(data)>0)
{
indx = max_indx;
array[indx] = data;//当前的最大值被删除了
}
else
{
indx = 1;//不替换
}
}
//向上检测
while(indx>1)
{
//当前元素与其父节点比较 若小，则交换 indx = indx/2
//否则 break
int pdx = indx/2;
if(((T)array[indx]).compareTo(((T)array[pdx]))<0)
{
Object tmp = array[indx];
array[indx] = array[pdx];
array[pdx]=tmp;
indx = pdx;
}else
{
break;
}
}
}
/**
* 删除堆顶元素
* 删除堆顶，用最后一个元素代替堆顶，向下检测保持堆性质
*
* @return
*/
public T remove()
{
T data = null;
if(current_size==0)
return null;
data = (T) array[1];
array[1] = array[current_size];
array[current_size] = null;
current_size -- ;
//根节点与左右子节点中最小元素交换
int indx = 1;
int min_indx =indx;
Object tmp = null;
while((min_indx=getMinIndx(indx))!=indx)
{
//indx 与 min_indx元素交换
tmp = array[indx];
array[indx]=array[min_indx];
array[min_indx]=tmp;
indx = min_indx;
}
return data;
}
private int getMinIndx(int indx)
{
T left = null;
T right = null;
if(indx*2>this.current_size)//没有子节点
return indx;
if(indx*2==this.current_size)
left = (T)array[indx*2];
else
{
left = (T)array[indx*2];
right =(T)array[indx*2+1];
}
if(right==null)
{
if(left.compareTo((T)array[indx])<0)
indx = indx*2;
}else
{
if(left.compareTo((T)array[indx])<0)
{
indx = indx*2;
if(right.compareTo((T)array[indx])<0)
indx = indx+1;
}
else if(right.compareTo((T)array[indx])<0)
{
indx = indx*2+1;
}
}
return indx;
}
public T peek()
{
if(this.current_size>0)
return (T) array[1];
return null;
}
public int capacity()
{
return array.length-1;
}
void printArray()
{
for(int i=1;i<=this.current_size;i++)
{
System.out.print(array[i].toString()+" ");
}
System.out.println("\n");
}
public Object [] getAll()
{
Object[] newArray = new Object[this.current_size];
System.arraycopy(array, 1, newArray, 0, current_size);
return newArray;
}
public static void main(String args[])
{
Integer array[] = new Integer[]{3,5,2,6,7,-1,8,0,9,-10};
LittleHeadFixedBinHeap heap = new LittleHeadFixedBinHeap(5,array);
heap.printArray();
}
}
分享到：
相关推荐
输入一个N位高精度的正整数，去掉其中任意K个数字后剩下的数字...写算法对给定的N和K，寻找一种方案使得剩下的数字组成的新数最小。 输入：N、K以及一个N位高精度的正整数 输出：剩下的数字组成的最小新数 如下图所示：
删数问题 Description 给定n 位正整数a，去掉其中任意k≤n 个数字后，剩下的数字按原次序排列组成一个 新的正整数。对于给定的n位正整数a 和正整数k，设计一个算法找出剩下数字组成的新数 最小的删数方案。 «...
描述部分提供了一个具体的例子，说明了如何找出数组中的最小K个数。例如，对于数组`[4, 5, 1, 6, 2, 7, 3, 8]`，我们要找的是最小的4个数，即`[1, 2, 3, 4]`。在示例1中，输入数组为`[3, 2, 1]`，K值为2，输出可以是...
在N个数字中，删除K个，使剩余的数字最小。
在C语言中，处理大数据集并找出其中最大的k个数或最小的k个数是一个常见的问题，这通常涉及到数据结构中的“堆”概念。堆是一种特殊的树形数据结构，满足以下性质：每个父节点的值要么大于等于其子节点（大顶堆），...
第三行输入一个正整数k，表示求该组测试例中的前k个最小元素。（设给出的每个整数序列中的元素是唯一的。） 输出：对于每个测试例输出一行，由k个整数组成，表示输入的n个整数中前k个最小元素。整数之间用一个空格隔...
标题 "js代码-最小k个数" 暗示了我们正在探讨JavaScript中关于找到数组里最小k个数的问题。这是一个常见的算法问题，通常在数据结构和算法的学习中出现，对于编程面试和优化数据处理非常有帮助。我们将深入讨论如何...
最小的k个数.md
本问题要求处理一个特定的数学挑战：给定一个由 `n` 位组成的正整数 `a` 和一个正整数 `k`（其中 `k ），任务是找到一种方法，通过删除 `a` 中的 `k` 个数字，使得剩余数字按照原有的顺序重新组合成一个新的正整数，...
在计算机科学领域，特别是数据处理和分析方面，“找到一组数中的前K个最大或最小的数”是一个常见而又重要的问题。这类问题不仅在日常开发工作中频繁出现，也是IT类考试的重点考察内容之一。本文旨在介绍几种解决这...
在计算机科学中，最小路径问题通常涉及到找到网络或图中两个节点之间最短的路径。这个问题在各种领域都有应用，例如路由选择、交通规划、电路设计等。在本例中，我们将探讨如何使用C语言来解决这个问题，主要涉及两...
总的来说，解决"求一个数组最小的两个数的下标"的问题，可以通过简单的线性搜索或者利用更高效的算法如优先队列来实现。在实际应用中，应根据数据规模和性能需求选择合适的方法。在VC6.0这样的集成开发环境中，我们...
本文实例讲述了Python实现查找最小的k个数。分享给大家供大家参考，具体如下： 题目描述 输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。 解法1 使用partition...
本文探讨的问题是“删数问题算法程序（排列成一个新的正整数）”，该问题要求从一个给定的正整数中删除指定数量的数字，使剩余数字按原有顺序排列形成的新数尽可能小。 **问题描述：** - 给定一个长度为 \( n \)（\...
java基础面试题最小的K个数提取方式是百度网盘分享地址
题目要求给定一个长度为 n 的正整数 a 和一个整数 k，要求删除该数中的 k 个数字，使得剩余数字按原有顺序排列后组成的数最小。 **问题描述**： - **输入**：多组测试数据（不超过50组），每组包含两个整数 a 和 k...
在给定的编程问题中，任务是找到两个已排序整数数组 `nums1` 和 `nums2` 中和最小的 `k` 对数字。这个问题属于算法的范畴，具体是组合优化问题，通常在数据结构和算法的学习中作为 LeetCode 等在线编程平台上的挑战...
在计算机科学中，"求第k小元素"是算法设计中的一个重要问题，它涉及到排序和查找的技巧。这个问题的目标是从一个未排序或者部分排序的数组或集合中找到第k个最小的元素，其中k通常是一个正整数。这个问题在数据分析...
c++ c++_剑指offer题解之最小的k个数
这是一个用C++写的简单算法,里面没用到什么高深的东西，就是基本的控制语句组成。