- 浏览: 882668 次
- 性别:
- 来自: 深圳
文章分类
- 全部博客 (509)
- android (55)
- CSS (23)
- eclipse (25)
- Data Structes and Algorithms (53)
- J2SE (87)
- Java_面试学习_j2se (26)
- java_面试学习_非技术 (13)
- java_gui (2)
- java_设计模式 (27)
- JDBC (10)
- java_web (15)
- hibernate (5)
- Oracle (37)
- Struts2 (7)
- Word-----dos (24)
- Jbpm (3)
- java小技巧 (8)
- math (1)
- flex (12)
- WebService (4)
- 生活 (9)
- 小框架或小语言 (27)
- spring (1)
- 面试~~~软实力 (7)
- jstat的用法 (1)
- jmap (1)
- 数据链路层和传输层的流量控制区别 (1)
- shell (0)
- 财商 (1)
- javascript (0)
- js研究 (1)
- 代码收集 (0)
最新评论
-
海尔群:
http://jingyan.baidu.com/articl ...
android加密 -
完美天龙:
------------------------- ...
asm----字节码操纵 -
houniao1990:
大神,请问 string 类型 定义为 oracle的 cha ...
hibernate注解 -
JamesQian:
Line:103
f.doFilter(msg);
是否需 ...
责任链模式_过滤器模式 -
sacoole:
好评
interview--- 如何从N个数中选出最大(小)的n个数?
题目:输入n个整数,输出其中最小的k个。
例如:输入1,2,3,4,5,6,7和8这8个数字,则最小的4个数字为1,2,3和4
思路:用一个k的容器,先放入K个数,然后接下来总是把最大数给踢出去。
用大顶堆,或者红黑树,大顶堆,大顶堆在O(1)得到已有的k个数字中的最大值,但需要O(logk)时间完成删除以及插入操作。红黑树通过把结点分为红、黑两种颜色并根据一些规则确保树是平衡的,从而保证在红黑树中查找、删除和插入操作都只需要O(logk)
public void getMinK(int[] arr,int k){
List<Integer> stack= new ArrayList<Integer>(); //里面放最小的k个数
for(int i=0;i<arr.length;i++){
}
}
-------------------------------------------------------------------------------------------
#include <stdio.h>
//已知(k1,k2……,kn)是堆,试写一个算法将(k1,k2,……,kn,kn+1)调整为堆。
//按此思想写一个从空堆开始一个一个填入元素的建堆算法
//(题示:增加一个k n+1后应从叶子向根的方向调整)
#define length 6
void HeadSort(int a[],int n);
void HeadAdjust(int a[],int s, int m);
void HeadAdjust(int *a,int head, int tail) {
int temp;
temp = a[head]; //若s=2 ,则rc = a[1]
for ( int j= 2*head; j <= tail; j= 2*j) {
if( j<tail && a[j]<a[j+1])
++j;
if( temp > a[j])
break;
a[head] = a[j];
head = j;
}
a[head] = temp;
//打印*********************
for(int i = 0 ; i < length; i++) {
printf("%d ",a[i]);
}
printf("/r/n");
//打印*********************打印结束
} // HeadAdjust
void HeadSort(int *a,int n) {
int i;
int tmp;
for( i = length/2 ; i > 0; --i) {
HeadAdjust(a,i,length);
}
//打印*********************
for(i = 0 ; i < length; i++) {
printf("%d ",a[i]);
}
printf("/r/n");
//**********************打印结束
tmp = a[0];
a[0] = a[length-1];
a[length-1] = tmp;
//打印**********************
for(i = 0 ; i < length; i++) {
printf("%d ",a[i]);
}
printf("/r/n");
//打印*********************打印结束
for(i = length-1; i>1; --i) {//////////////
printf("i's value:%d/n",i);
HeadAdjust(a,0,i);
tmp = a[0];
a[0] = a[i];
a[i] = tmp;
}
printf("i's value:%d/n",i);
}
int main() {
int n ;
int a[1000] ;
printf("Input the Number you want to Sort :");
scanf("%d",&n);
printf("Please Input the values :");
for(int i=0;i<n;++i)
scanf("%d",&a[i]);//输入时,不能在"%d"内多出任何空格,否则需要多敲一个字符********************Important
printf("/r/n");
HeadSort(a,n);
for(i=0;i<n;++i)
printf("%d ",a[i]);
printf("/r/n");
return fals
例如:输入1,2,3,4,5,6,7和8这8个数字,则最小的4个数字为1,2,3和4
思路:用一个k的容器,先放入K个数,然后接下来总是把最大数给踢出去。
用大顶堆,或者红黑树,大顶堆,大顶堆在O(1)得到已有的k个数字中的最大值,但需要O(logk)时间完成删除以及插入操作。红黑树通过把结点分为红、黑两种颜色并根据一些规则确保树是平衡的,从而保证在红黑树中查找、删除和插入操作都只需要O(logk)
public void getMinK(int[] arr,int k){
List<Integer> stack= new ArrayList<Integer>(); //里面放最小的k个数
for(int i=0;i<arr.length;i++){
}
}
-------------------------------------------------------------------------------------------
#include <stdio.h>
//已知(k1,k2……,kn)是堆,试写一个算法将(k1,k2,……,kn,kn+1)调整为堆。
//按此思想写一个从空堆开始一个一个填入元素的建堆算法
//(题示:增加一个k n+1后应从叶子向根的方向调整)
#define length 6
void HeadSort(int a[],int n);
void HeadAdjust(int a[],int s, int m);
void HeadAdjust(int *a,int head, int tail) {
int temp;
temp = a[head]; //若s=2 ,则rc = a[1]
for ( int j= 2*head; j <= tail; j= 2*j) {
if( j<tail && a[j]<a[j+1])
++j;
if( temp > a[j])
break;
a[head] = a[j];
head = j;
}
a[head] = temp;
//打印*********************
for(int i = 0 ; i < length; i++) {
printf("%d ",a[i]);
}
printf("/r/n");
//打印*********************打印结束
} // HeadAdjust
void HeadSort(int *a,int n) {
int i;
int tmp;
for( i = length/2 ; i > 0; --i) {
HeadAdjust(a,i,length);
}
//打印*********************
for(i = 0 ; i < length; i++) {
printf("%d ",a[i]);
}
printf("/r/n");
//**********************打印结束
tmp = a[0];
a[0] = a[length-1];
a[length-1] = tmp;
//打印**********************
for(i = 0 ; i < length; i++) {
printf("%d ",a[i]);
}
printf("/r/n");
//打印*********************打印结束
for(i = length-1; i>1; --i) {//////////////
printf("i's value:%d/n",i);
HeadAdjust(a,0,i);
tmp = a[0];
a[0] = a[i];
a[i] = tmp;
}
printf("i's value:%d/n",i);
}
int main() {
int n ;
int a[1000] ;
printf("Input the Number you want to Sort :");
scanf("%d",&n);
printf("Please Input the values :");
for(int i=0;i<n;++i)
scanf("%d",&a[i]);//输入时,不能在"%d"内多出任何空格,否则需要多敲一个字符********************Important
printf("/r/n");
HeadSort(a,n);
for(i=0;i<n;++i)
printf("%d ",a[i]);
printf("/r/n");
return fals
发表评论
-
j2se---jmap看性能
2011-08-05 09:41 1046dump一下内存jmap -dump:format=b,fil ... -
程序员面试题精选100题(60)-判断二叉树是不是平衡的
2011-07-24 15:33 6772题目:输入一棵二叉树的根结点,判断该树是不是平衡二叉树。如果某 ... -
程序员面试题精选100题(58)-八皇后问题
2011-07-24 12:22 1121题目:在8×8的国际象棋上摆放八个皇后,使其不能相互攻击,即任 ... -
程序员面试题精选100题(57)-O(n)时间的排序
2011-07-24 12:02 1196题目:某公司有几万名员工,请完成一个时间复杂度为O(n)的算法 ... -
程序员面试题精选100题(55)-不用+、-、×、÷数字运算符做加法
2011-07-24 11:15 1719题目:写一个函数,求两个整数的之和,要求在函数体内不得使用+、 ... -
程序员面试题精选100题(51)-顺时针打印矩阵
2011-07-24 09:35 1636题目:输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个 ... -
程序员面试题精选100题(50)-树为另一树的子结构
2011-07-23 20:24 1077题目:二叉树的结点定 ... -
程序员面试题精选100题(49)-复杂链表的复制
2011-07-23 19:49 1350题目:有一个复杂链表,其结点除了有一个m_pNext指针指向下 ... -
程序员面试题精选100题(48)-二叉树两个结点的最低共同父结点
2011-07-21 19:17 2155题目:二叉树的结点定义如下: struct TreeNode ... -
程序员面试题精选100题(47)-数组中出现次数超过一半的数字
2011-07-21 18:56 1117题目:数组中有一个数字出现的次数超过了数组长度的一半,找出这个 ... -
程序员面试题精选100题(46)-对称子字符串的最大长度
2011-07-21 18:46 1594题目:输入一个字符串,输出该字符串中对称的子字符串的最大长度。 ... -
程序员面试题精选100题(45)-Singleton
2011-07-21 18:38 973不说了。。。见设计模式 -
程序员面试题精选100题(44)-数值的整数次方
2011-07-19 22:22 1553题目:实现函数double Pow ... -
程序员面试题精选100题(43)-n个骰子的点数
2011-07-19 20:02 2204题目:把n个骰子扔在地上,所有骰子朝上一面的点数之和为S。输入 ... -
程序员面试题精选100题(42)-旋转数组的最小元素
2011-07-19 18:56 1009题目:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数 ... -
程序员面试题精选100题(41)-把数组排成最小的数
2011-07-17 23:35 1237题目:输入一个正整数数组,将它们连接起来排成一个数,输出能排出 ... -
程序员面试题精选100题(38)-输出1到最大的N位数
2011-07-17 22:49 1560题目:输入数字n,按顺序输出从1最大的n位10进制数。比如输入 ... -
程序员面试题精选100题(37)-寻找丑数
2011-07-17 22:15 2563题目:我们把只包含因子2、3和5的数称作丑数(Ugly Num ... -
程序员面试题精选100题(36)-在字符串中删除特定的字符
2011-07-17 21:17 1016题目:输入两个字符串,从第一字符串中删除第二个字符串中所有的字 ... -
程序员面试题精选100题(35)-找出两个链表的第一个公共结点
2011-07-17 20:32 1261题目:两个单向链表,找出它们的第一个公共结点。 两个链表如果 ...
相关推荐
输出一组元素中的最小的k个元素。例如数据集为:{1、8、3、6、5、4、7、2},则最小的4个数字为1,2,3和4。 【基本要求】 由随机数产生测试数据,测试数据不小于10000个,测试k的不同取值对算法的影响,如k=10、50、...
在计算机科学中,"算法中最小K元素的选择问题"是一个重要的数据结构和算法主题,它涉及到从一个无序或有序的数组中找到第K小(或大)的元素。这个问题在各种应用场景中都有广泛的应用,比如数据库查询优化、排序算法...
这个问题的基本目标是从一个未排序或已排序的数组或集合中找出第k个最小的元素。这里我们将深入探讨三种方法来解决这个问题:中位选择法、随机选择查找以及排序查找。 1. **中位选择法**: 中位选择法是一种高效...
3. 计算基准元素所在位置的索引,如果这个索引等于k-1,则基准就是第k个最小元素;如果索引小于k-1,说明第k个最小元素在基准右边的子数组中;如果索引大于k-1,则第k个最小元素在基准左边的子数组中。 4. 递归地在...
创建一个大小为k的最小堆,将数组的前k个元素放入堆中。之后,遍历数组剩余的元素,如果元素小于堆顶元素(即第k小元素),则替换堆顶元素并重新调整堆。最后,堆顶元素即为第k小元素。这种方法的时间复杂度为O(n ...
5. **查找最小k个元素**: 使用最小堆,将前k个元素放入堆中,之后依次与堆顶元素比较,若新元素小于堆顶,则替换并调整堆。最终堆中的k个元素就是最小的k个。 6. **分配计数问题**: 这个问题可以通过计数排序或...
5. **查找最小k个元素** 快速选择算法可以用来在O(n)平均时间复杂度内找出数组中的最小k个元素。该算法基于快速排序的思想,每次选取一个基准值,将小于基准的元素放到基准左边,大于基准的元素放到右边,然后根据k...
5. **查找最小k个元素**: 快速选择或堆排序是解决这类问题的有效方法。快速选择可以在平均情况下达到O(n)的时间复杂度,堆排序可以保证在最坏情况下也保持O(n log k)的时间复杂度。可以构建一个大小为k的小顶堆,...
5. **查找最小k个元素**: 快速选择或堆排序可以解决这个问题。快速选择可以在平均O(n)的时间内找到第k小的元素。堆排序则可以将数组构建成一个最小堆,然后依次取出k个最小元素。 6. **数组分配问题**: 这是一...
5. **查找最小k个元素**: 快速选择或堆排序可以高效地找到数组中的最小k个元素。快速选择基于快速排序的思想,平均时间复杂度为O(n),最坏情况下为O(n^2),而堆排序始终保证O(n log n)的时间复杂度。 6. **统计...
5. **查找最小 k 个元素**:可以使用优先队列(堆)来解决,每次取出最小元素并维护堆的大小为 k,最后堆中的 k 个元素即是最小的 k 个数。时间复杂度为 O(n log k)。 6. **统计每个数的出现次数**:可以使用哈希表...
5. **查找最小k个元素** 使用优先队列(堆)或者快速选择算法可以高效地找到数组中最小的k个元素。堆可以在O(n log k)时间内完成,而快速选择的平均时间复杂度为O(n)。 6. **统计数字出现频率** 这是一个计数问题...
在给定的标题“查找第k小2”中,我们可以推断这是一个关于查找第k小元素的算法问题的第二个版本,可能与之前的实现有所不同或者更进阶。描述提到“完成算法课程作业,随机生成1000个数字,短时间内找到第k小”,这...
2. **优先队列/堆**:使用最小堆来存储前K个元素,每次插入新元素时,如果堆的大小超过K,则将堆顶元素(最大值)移除,这样可以保证堆中始终包含当前的K个最小元素。 3. **线性时间复杂度的解决方案**:例如,可以...
5. **查找最小k个元素**: 使用快速选择或堆排序可以解决。快速选择可以在平均情况下达到O(n)的时间复杂度,堆排序则能保证O(n log k)的时间复杂度,用于找出最小的k个元素。 6. **数字分配问题**: 这是一个计数...
5. **查找最小k个元素** 快速选择算法可以解决这个问题,它基于快速排序的分治思想,但不需要完全排序。在每次划分时,选择一个基准元素,将小于基准的元素放到它的左边,大于或等于的元素放到右边。如果k在基准的...
5. **查找最小k个元素**: 使用优先队列(堆)解决,每次将新元素与堆顶元素比较,如果较小则替换堆顶元素并调整堆。重复此过程,直到找到k个最小元素。 6. **频率分配问题**: 可以用哈希表记录上排每个数出现的...
当弹出的元素个数等于k-1时,堆顶剩下的元素就是第k小的元素。堆排序法的时间复杂度为O(n log n)。 3. **线性时间复杂度的解决方案**: 当数据集支持随机访问时,可以使用“最小堆+跳跃”算法,也称为“三数取中”...
5. **查找最小k个元素**: - 可以使用快速选择算法,该算法是快速排序的变体,专门用于寻找数组中的第k小元素。在平均情况下,时间复杂度为O(n),最坏情况下为O(n^2)。 6. **腾讯面试题:数组分配问题**: - 这是...