`
YuHuang.Neil
  • 浏览: 188884 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

Algorithm 05 : 给定一个数组,寻找第K大的数

阅读更多
给定一个无序数组,求数组中第K大的数。

答:求一个数组中第K大数可以借用快速排序算法的思想,主要思路如下:
      (1)在数组中随机选择一个数作为支点。
      (2)将比作为支点数大的所有数放在这个支点的左边,支点放在数组中间的位置。
      (3)设支点左边元素的个数为L,那么可以分以下三种情况:
              (a)当K=L的时候,直接返回支点即是所要求的第K大的数。
              (b)当K<L的时候,在支点左边的数中继续寻找第K大的数。
              (c)当K>L的时候,在支点右边的数中继续寻找第(K-L)大的数。

         基于上述想法的代码实现如下:

/** @author YuHuang
   * @version 2011-10-11
   * This program is only for algorithm training.
   *
   */

import java.lang.*;
import java.lang.RuntimeException;
import java.util.Random;

public class FindKthNumber {
        private int[] dataArray;
        private Random random = new Random();

        private FindKthNumber() {}

        public FindKthNumber(int[] dataArray){
                if(dataArray!=null && dataArray.length!=0){
                        this.dataArray = dataArray;
                }else{
                        throw new RuntimeException("Array should not be null!");
                }
        }

        public int doFind(int left,int right,int k){
                int pivot;
                int m=left;
                int count=1;

                System.out.println("k="+k);
                if(k<=0||k>right-left+1){
                        return -1;
                }

                pivot=left+(java.lang.Math.abs(random.nextInt()))%(right-left+1);
                swap(left,pivot);

                for(int index = left+1;index<=right;++index){
                        if(this.dataArray[index]>this.dataArray[left]){
                                swap(++m,index);
                                ++count;
                        }
                }

                swap(left,m);

                if(k<count){
                        return doFind(left,m-1,k);
                }else if(k>count){
                        return doFind(m+1,right,k-count);
                }else{
                        return m;
                }

        }

        private void swap(int fIndex,int lIndex){
                int temp = this.dataArray[fIndex];
                this.dataArray[fIndex]=this.dataArray[lIndex];
                this.dataArray[lIndex]=temp;
        }

        public static void main(String[] args){
                int[] dataArray=new int[]{1,6,3,8,9,18,22,45,11,99};

                try{
                        FindKthNumber fkn = new FindKthNumber(dataArray);
                        int k=4;
                        int result=fkn.doFind(0,dataArray.length-1,k);
                        result = result==-1? result:dataArray[result];
                        System.out.println("The "+k+"th number in dataArray is "+result);
                }catch(Exception e){
                        e.printStackTrace();
                }
        }
}





运行的结果如下:
Lab-Computer-0db2f6:JavaExercises labuser$ java FindKthNumber
k=4
k=4
k=3
The 4th number in dataArray is 18

知识扩展:容易想到对上面的算法进行小小的改造就可以求出一个给定数组中的前K大的所有数字。即在输出的时候,如果result的值不为-1,则输出数组中0~result之间的所有数就是所要求解的前K大数的集合。






分享到:
评论
1 楼 yjc2020 2014-03-05  
求第几大的数后还要给出其在原数组中的位置,你这个是不是还要再遍历一次

相关推荐

    最大和连续子数组1

    问题定义:给定一个整数数组 A[1...n],找到一个连续子数组 A[i...j],使得它的和最大,即求解 max(A[i] + A[i+1] + ... + A[j]),其中 1 ≤ i ≤ j ≤ n。 这个问题有多种解决方法,其中最著名的是 Kadane's ...

    《算法最优解(第一版)》剑指Offer题解校招求职刷题必备.docx

    11. **和为S的两个数字**:给定一个整数数组和目标和S,找出数组中和为目标和的两个数,可以使用哈希表进行一次遍历来解决。 12. **和为S的连续正整数序列**:找到连续正整数序列的和为S,可以通过公式n*(n+1)/2与S...

    算法-leetcode-剑指offer上的题很多

    - **堆排序(Heap Sort)**: 利用堆这种数据结构所设计的一种排序算法,将整个待排序序列构造成一个大顶堆。 - **计数排序(Counting Sort)**: 根据数组下标来确定元素的正确位置。 - **桶排序(Bucket Sort)**: 按照...

    面试常考算法必刷题库1

    1. **三数之和**:给定一个整数数组,找出所有三个数的组合,使得它们的和等于给定的目标值。这通常涉及到双指针技巧和哈希表的使用。 2. **子集**:找出给定数组的所有可能子集。这个问题可以通过递归或动态规划来...

    面试时常见的智力题

    如斐波那契数列,给定一个整数n,求第n个斐波那契数。斐波那契数列定义为F(0)=0,F(1)=1,后续项为前两项之和。可以通过动态规划或矩阵快速幂优化来求解。 5. **最短路径问题**: 在带权图中寻找两点间的最短路径...

    python笔试例题(快速排序、二分查找、最长无重复子串、最长回文串长度、输出数组中两数相加=target的下标、用两.pdf

    5. **输出数组中两数相加=target的下标**:这是一道线性查找问题,给定一个数组和一个target值,需要找出数组中哪些元素之和等于target,并返回它们的下标。可以使用双指针法,从数组两端开始向中间移动,直到找到和...

    MyLib(For ACM)

    - **二分查找(大于等于V的第一个值)**:寻找第一个大于等于给定值的元素。 - **所有数位相加**:计算一个数字的所有数位之和。 #### 数论 - **递推求欧拉函数PHI(I)**:递归计算欧拉函数φ(i)。 - **单独求欧拉...

    c++-c++编程基础之leetcode题解第15题三数之和.zip

    三数之和的问题是这样的:给定一个整数数组`nums`,目标是找到所有使得`nums[i] + nums[j] + nums[k] = 0`的数组下标`i`, `j`, `k`,其中`0 &lt;= i &lt; j &lt; k 。这实际上是一个经典的二维搜索问题,可以通过排序和双指针...

    ACM/ICPC常用算法的代码库(吉林大学版,强烈推荐)

    - **二分查找(大于等于V的第一个值)**:查找第一个大于等于给定值的元素位置。 - **所有数位相加**:计算一个整数中所有数字的总和。 #### Number数论 - **递推求欧拉函数PHI(I)**:计算欧拉函数φ(i),即小于i...

    算法——Dijkstra’s algorithm求最短路径并打印出路径的各个节点

    2. **修改数据结构**:为了存储每个节点的最短路径跳数,我们需要一个新的数组 \(D\) 来记录这些信息。 3. **更新逻辑**:在 Dijkstra's 算法的核心循环中,我们需要更新节点间的跳数而非实际路径长度。 4. **输出...

    常用算法代码常用算法代码常用算法代码

    - HLPP最大流:一个最大流算法。 - 最小费用流:解决网络流中最小化成本的问题。 ### 数据结构 #### 树形结构 - 左偏树合并复杂度O(LOGN):一种特殊的堆数据结构,合并操作的时间复杂度为对数级别。 - 树状数组:...

    acm_常用模版_素数标记_树状数组_线段树等

    检查一个大整数是否为素数通常采用 Miller-Rabin素数检验或者AKS素数检验,这些算法在概率上能有效识别素数,但不是确定性的。 **最小生成树**: 最小生成树算法,如Prim或Kruskal,用于找到一个加权无向图的边集合...

    经典算法源代码(for ACM)

    - **最小生成森林问题(K颗树)O(MlogM)**:当图不连通时,需要构造一个包含K棵树的最小生成森林。可以使用Kruskal算法或者Prim算法的变体来解决。 **其他图论问题**: - **TARJAN强连通分量**:一种高效的强连通分量...

    常见:算法面试题总结 (2)1

    将n个数字插入一个最小堆,每次取出堆顶元素(最小元素),重复k次即可得到最小的k个数。 6. **计数问题**: 这是一个统计频率的问题,可以使用哈希表(字典或HashMap)来解决。遍历上排的数,将每个数作为键,...

    吉大acm模板

    - **定义**: 给定一个整数n,欧拉函数φ(n)表示不大于n且与n互质的正整数个数。 - **应用场景**: 密码学、数论问题求解等。 - **算法步骤**: - 使用递推公式计算。 ##### 4.2 单独求欧拉函数PHI(X)(Euler's ...

    c++-c++编程基础之leetcode题解第16题最接近的三数之和.zip

    题目描述:给定一个包含n个整数的数组nums,判断nums中是否存在三个元素a,b,c,使得a + b + c = 0。找出所有满足条件且不重复的三元组。 解题思路: 1. 首先,我们可以对数组进行排序,这样可以减少后续比较的...

    Algorithm-MatrixChainMultiply.jl.zip

    算法的基本思想是采用自底向上的动态规划方法,构建一个二维数组dp,其中dp[i, j]表示矩阵i到j的最优乘法方案所需的最小运算次数。通过递推公式计算dp数组,再根据dp数组回溯得到最优的乘法顺序。 递推公式通常表示...

    西安电子科技大学期末数据结构试题及详细答案.docx

    - **快速排序:** 通过选取一个“基准”元素,将数组分为两个子数组,左边的元素都比基准小,右边的元素都比基准大,然后递归地对这两个子数组进行同样的操作。 - **空间复杂度分析:** - 最佳情况下的空间复杂度为...

Global site tag (gtag.js) - Google Analytics