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

从一个无序的数字序列中查找出前K个最大的数字[递归方式]

阅读更多

题设:

 /**
 * Created by Lanxiaowei
 * Craated on 2016/12/13 9:46
 * 从一个无序的数字序列中查找出前K个最大的数字,
 * 要求返回的K个数字在目标无序数组中是前K个最大的,但是不要求这前K个数字是有序的
 * 比如:8 9 5 0 6 2 7 1 4 3 且K = 5,那么最终应该返回
 * 9 8 7 6 5 或者 6 5 8 7 9
 */
public class TopKProblems {
    public static void main(String[] args) {
        int k = 5;
        int[] array = {8, 9, 5, 0, 6, 2, 7, 1, 4, 3};
        List<Integer> result = new ArrayList<Integer>();
        findTopKBig(array,0,array.length, k,result);
        if(null == result || result.size() <= 0) {
            System.out.println("No results.");
            return;
        }
        for(int i=0; i < result.size(); i++) {
            System.out.print(result.get(i) + " ");
        }
    }

    /**
     * 从从一个无序的数字序列中查找出前K个最大的数字
     * @param array     待查找的无序数组
     * @param offset    查找的起始偏移量
     * @param n         待查找的前N个
     * @param k         表示最终需要返回的前K个
     * @return
     */
    public static List<Integer> findTopKBig(int[] array,int offset,int n,int k,List<Integer> result) {
        if(n <= 0) {
            return null;
        }
        if(result == null) {
            result = new ArrayList<Integer>();
        }
        //如果k >= n,则直接返回整个数组即可
        if(k >= n) {
            for(int i=offset; i < offset + n; i++) {
                result.add(array[i]);
            }
            return result;
        }
        //a1表示中间那个元素,a1将整个数组分成左大右小两部分
        int a1 = array[offset];
        //头指针
        int y = offset;
        //尾指针
        int z = offset + n - 1;
        int n1 = 0;
        int n2 =0;
        while (y < z) {
            //从头指针往尾指针遍历
            while (array[z] <= a1 && y < z) {
                z--;
            }
            if(y < z) {
                array[y] = array[z];
            }
            //从尾指针往头指针遍历
            while (array[y] > a1 && y < z) {
                y++;
            }
            if(y < z) {
                array[z] = array[y];
            }
        }
        //此时头尾指针重合,找到a1的位置即中间的那个元素
        array[y] = a1;
        //计算a1前面的元素总个数即左边比较大的元素总个数
        n1 = y - offset + 1;
        //计算a1后面的元素总个数即右边比较小的元素总个数
        n2 = n - n1;
        //如果k >= n1,那么直接返回前n1个元素
        if(n1 <= k) {
            for(int i=offset; i <= y; i++) {
                result.add(array[i]);
            }
        }
        //如果k < n1,那么就需要在[offset,n1 - 1]范围内查找前K个最大的数字
        if(n1 > k) {
            return findTopKBig(array,offset,n1 - 1 ,k,result);
        }
        //如果k > n1,那么就需要在[y + 1,n2]范围内查找前K个最大的数字,这里的y+1其实表示的就是a1后面的那个元素即
        //从a1后面的n2个比较小元素里查找剩下的符合要求的数字
        if(n1 < k) {
            return findTopKBig(array,y + 1,n2,k - n1,result);
        }
        return result;
    }
}

 

 

 

分享到:
评论

相关推荐

    迭代顺序查找、递归顺序查找、二分查找

    在每次递归调用中,算法检查当前元素是否为目标,如果是则返回,否则继续查找下一个元素。递归查找虽然逻辑清晰,但额外的函数调用开销可能导致性能下降,特别是在深度大的递归树上。时间复杂度同样为O(n)。 **二分...

    排序(下):如何用快排思想在O(n)内查找第K大元素?.pdf

    本篇文章探讨了一个有趣且实用的计算机科学问题:如何利用快速排序的思想,在线性时间内找出一个无序数组中的第K大元素。这个问题不仅考验着我们对数据结构和算法的理解,还挑战着我们运用已有知识解决新问题的能力...

    算法:求第k小元素

    在计算机科学中,"求第k小元素"是算法设计中的一个重要问题,它涉及到排序和查找的技巧。这个问题的目标是从一个未排序或者部分排序的数组或集合中找到第k个最小的元素,其中k通常是一个正整数。这个问题在数据分析...

    选择第k小问题.zip

    在计算机科学中,"选择第k小问题"是一个常见的算法问题,主要涉及到数据排序和查找。这个问题要求在一组无序的元素中找到第k小(或第k大)的元素,而不必对整个序列进行完全排序。在本案例中,我们关注的是如何使用...

    无序表的查找与排序程序

    顺序查找是最简单的,从表的第一项开始逐个比较,直到找到目标或遍历完整个表。折半查找适用于有序表,通过比较中间元素来减少查找次数。分块查找则将数据分成若干块,先在索引块中查找,再在找到的块内进行顺序查找...

    文件读出数组进行选择排序和二分查找(java)

    它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。在Java中,你可以实现一个选择排序的函数,遍历数组,找到最小元素并交换到已排序...

    查找字符组合(数字版).zip_组合

    在VB(Visual Basic)编程...总的来说,"查找字符组合(数字版)"是一个关于VB编程和组合数学的实际应用,通过学习和理解这个项目,我们可以增强在字符和数字处理方面的编程技能,更好地掌握VB中的字符串操作和算法设计。

    采用二分查找法和顺序查找法查找元素的下标

    顺序查找的基本思想是从数据序列的第一个元素开始,逐个与目标值进行比较,直到找到目标元素或者遍历完整个序列。如果找到目标元素,返回其下标;如果遍历完序列仍未找到,通常返回一个特殊值,如-1表示未找到。虽然...

    C语言数据结构 广工 作业系统 09.查找

    - 函数 `int Search(SSTable s, KeyType k)` 实现了线性查找的功能,用于在一个 `SSTable` 中查找指定关键字 `k` 的位置。 - 首先设置 `a.elem[0].key = k` 以便能够返回 0 如果没有找到。 - 通过循环遍历数组,...

    寻找第k小元素(vc)

    首先找到数组中第一个大于等于k的元素,然后在此元素之前的子数组中再寻找第k-1小的元素。这种方法适用于有序数组,时间复杂度为O(log n)。 6. **优先队列(堆)**:C++标准库提供了一个名为`&lt;queue&gt;`的头文件,...

    Python递归调用实现数字累加的代码

    在这个`sum_numbers`函数中,我们定义了一个递归出口(base case),即当输入的数字`num`等于1时,函数返回1。这是因为1是1个单位的最小值,不需要再进行递归。对于其他大于1的`num`值,函数会递归地调用自身,将`...

    分治法解快速排序,对称搜索及最大字段和

    1. **选择基准**:从数组中选取一个元素作为基准,可以选择第一个、最后一个或者中间元素,也可以使用随机方法。 2. **分区操作**:重新排列数组,使得所有小于基准的元素位于其左侧,所有大于基准的元素位于其右侧...

    C 二分查找算法.rar

    递归版本的二分查找通常会有一个基线条件(即数组为空或只剩一个元素)和一个递归情况(将问题分解为更小的部分)。递归函数会不断调用自身,每次都将问题规模减半,直到找到目标值或搜索范围为空。 相比之下,顺序...

    数据结构(查找)习题及答案

    - 递归算法OutputNLT用于从大到小输出二叉排序树中所有关键字值不小于x的数据元素,其时间复杂度为O(log2n+m),其中n是排序树中结点数,m是输出的关键字个数。 这些知识点是数据结构中查找算法的基础,理解和掌握...

    查找第i小的元素

    标题中的“查找第i小的元素”是指在一组无序数据中找到第i个最小的元素,例如在未排序的数组或集合中找到第k小的元素,这是一个常见的算法问题,广泛应用于各种数据结构和算法的实践中。这个问题的解决方法通常涉及...

    排序与查找(综合实验报告).pdf

    排序算法是数据结构中的一种基本算法,用于将一个无序的数据序列变得有序。常见的排序算法包括冒泡排序、选择排序、插入排序、归并排序、快速排序等。每种排序算法都有其特点和优缺,选择合适的排序算法取决于具体...

    有关于折半查找的问题

    2. **边界条件处理**:在查找过程中,要正确处理边界条件,例如当搜索区间为空或只剩一个元素时,应停止查找并给出相应结果。 3. **效率分析**:折半查找的时间复杂度为O(log n),其中n是数组的大小。相比于线性查找...

    数据结构中的查找和排序C语言实现代码

    线性查找是最简单的方法,从数据集合的第一个元素开始逐个比较,直到找到目标元素或遍历完整个集合。二分查找则适用于有序数据,通过不断缩小搜索范围来提高效率。哈希查找利用哈希表将数据映射到索引,达到近乎常数...

    408二轮-查找.pdf

    在顺序查找中,从数组的第一个元素开始,逐个比较目标元素与数组中的元素,直到找到目标元素或者搜索完整个数组。其平均查找长度(Average Search Length, ASL)等于元素个数n加上失败查找的次数,即ASL = n + 失败...

    数据结构中的查找和排序

    线性查找是最基础的方法,它从数据集合的第一个元素开始逐个比较,直到找到目标元素或遍历完整个集合。二分查找则适用于有序数组,通过不断将查找区间减半来提高效率。哈希查找利用哈希函数将数据映射到表的特定位置...

Global site tag (gtag.js) - Google Analytics