`
逆风的香1314
  • 浏览: 1437088 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

编程之美-得到无序数组中最大K个数

阅读更多

原文看这里:

题目描述:
问:有很多个无序的数,我们姑且假定他们各不相等,怎么选出其中最大的若干个数呢?
答:可以这样写:int array[100] 。。。
问:好,如果有更多的数呢?
答:那可以改为 int array[1000] ...
问:如果我们有很多的数,比如一亿个,怎么办?
答:我们可以写 float array[100000000] 。。。
问:这样的程序能编译运行吗?
答:嗯... 我没写过那么多的0 .....


以下是各种实现的代码,我们就不用1亿个数字测试了,如果真的有那么多,保存为文件,用InputStream一边读取,一边处理好了:

注意:代码里面的大部分for循环,都可以改成从InputStream进行读取,int[]参数也是一样。这样就可以处理大数据量了。
  1. import java.util.ArrayList;
  2. import java.util.Collections;
  3. import java.util.List;
  4. /**
  5.  * 得到无序数组的最大的K个数据。
  6.  * 
  7.  * @author 老紫竹 java2000.net
  8.  */
  9. public class ArrayFind {
  10.   public static void main(String[] args) {
  11.     int[] arrNum = { 15835872568495226163313656513334,
  12.         2423647444 };
  13.     List<Integer> arr = new ArrayList<Integer>(arrNum.length);
  14.     for (int num : arrNum) {
  15.       arr.add(num);
  16.     }
  17.     List<Integer> arrBak = new ArrayList<Integer>(arr);
  18.     int k = 5;
  19.     find1(arr, k);
  20.     //
  21.     //
  22.     arr.clear();
  23.     arr.addAll(arrBak);
  24.     List<Integer> rtn = find2(arr, k);
  25.     for (int num : rtn) {
  26.       System.out.print(num + ",");
  27.     }
  28.     System.out.println();
  29.     //
  30.     //
  31.     arr.clear();
  32.     arr.addAll(arrBak);
  33.     find3(arr, k);
  34.     //
  35.     //
  36.     arr.clear();
  37.     arr.addAll(arrBak);
  38.     List<Integer> rtn4 = find4(arr, k);
  39.     for (int num : rtn4) {
  40.       System.out.print(num + ",");
  41.     }
  42.     System.out.println();
  43.   }
  44.   /**
  45.    * 标准排序算法。
  46.    * 
  47.    * @param arr
  48.    * @param k
  49.    */
  50.   public static void find1(List<Integer> arr, int k) {
  51.     Collections.sort(arr);
  52.     for (int i = arr.size() - 1; i > arr.size() - k - 1; i--) {
  53.       System.out.print(arr.get(i) + ",");
  54.     }
  55.     System.out.println();
  56.   }
  57.   /**
  58.    * 大小组分组方法。
  59.    * 
  60.    * @param S
  61.    * @param k
  62.    * @return
  63.    */
  64.   public static List<Integer> find2(List<Integer> S, int k) {
  65.     if (k <= 0) {
  66.       return new ArrayList<Integer>();
  67.     }
  68.     if (S.size() <= k) {
  69.       return S;
  70.     }
  71.     List<Integer>[] rtn = Partition(S);
  72.     List<Integer> Sa = rtn[0];
  73.     List<Integer> Sb = rtn[1];
  74.     List<Integer> R = find2(Sa, k); // 找大的一组里面最大的k个
  75.     if (Sa.size() < k) {// 如果大的分组不足,则加上小的一组里面不够的数量
  76.       R.addAll(find2(Sb, k - Sa.size()));
  77.     }
  78.     return R;
  79.   }
  80.   private static List<Integer>[] Partition(List<Integer> S) {
  81.     ArrayList<Integer> Sa = new ArrayList<Integer>();
  82.     ArrayList<Integer> Sb = new ArrayList<Integer>();
  83.     int p = S.get(0);
  84.     int element;
  85.     for (int i = 1; i < S.size(); i++) {
  86.       element = S.get(i);
  87.       if (element > p) {
  88.         Sa.add(element);
  89.       } else {
  90.         Sb.add(element);
  91.       }
  92.     }
  93.     if (Sa.size() < Sb.size()) {
  94.       Sa.add(p);
  95.     } else {
  96.       Sb.add(p);
  97.     }
  98.     ArrayList<Integer>[] rtn = new ArrayList[2];
  99.     rtn[0] = Sa;
  100.     rtn[1] = Sb;
  101.     return rtn;
  102.   }
  103.   public static List<Integer> find3(List<Integer> S, int K) {
  104.     double Vmin = 0;
  105.     double Vmax = 1000;
  106.     double delta = 0.5;
  107.     double Vmid;
  108.     while (Vmax - Vmin > delta) {
  109.       Vmid = Vmin + (Vmax - Vmin) * 0.5;
  110.       int count = 0;
  111.       for (int n : S) {
  112.         if (n >= Vmid)
  113.           count++;
  114.         if (count >= K)
  115.           break;
  116.       }
  117.       if (count >= K) {
  118.         Vmin = Vmid;
  119.       } else {
  120.         Vmax = Vmid;
  121.       }
  122.     }
  123.     for (int s : S) {
  124.       if (s > Vmin) {
  125.         System.out.print(s + ",");
  126.       }
  127.     }
  128.     System.out.println();
  129.     return null;
  130.   }
  131.   /**
  132.    * 使用一个长度为K的小列表。
  133.    * 
  134.    * @param S
  135.    * @param K
  136.    * @return
  137.    */
  138.   public static List<Integer> find4(List<Integer> S, int K) {
  139.     List<Integer> rtn = new ArrayList<Integer>(K);
  140.     for (int i = 0; i < K; i++) {
  141.       rtn.add(S.get(i));
  142.     }
  143.     Collections.sort(rtn);
  144.     int min = rtn.get(0);
  145.     int current;
  146.     for (int i = K; i < S.size(); i++) {
  147.       current = S.get(i);
  148.       if (current > min) {
  149.         rtn.remove(0);
  150.         rtn.add(current);
  151.         Collections.sort(rtn);
  152.         min = rtn.get(0);
  153.       }
  154.     }
  155.     return rtn;
  156.   }
  157. }

运行结果
474,87,65,49,36,
474,87,65,49,36,
87,49,36,65,36,474,
36,49,65,87,474,
分享到:
评论

相关推荐

    python 实现在无序数组中找到中位数方法

    在Python编程中,寻找无序数组的中位数是一项常见的任务,特别是在数据分析和算法设计中。中位数是将一组数值按大小顺序排列后位于中间位置的数,对于偶数个数值,中位数是中间两个数的平均值。在不使用排序的情况下...

    Python实现查找数组中任意第k大的数字算法示例

    在一组无序的数值中,第k大的数字是指除去其中最大的k-1个数字后剩下的那个最大值。例如,对于数组[3, 5, 6, 7, 2, -1, 9, 3],第5大的数字是6,因为它在去除数组中的前4个最大元素(9, 7, 6, 5)后剩余的最大值。 ...

    微软技术面试-寻找最大的K个数

    本篇文章讨论了一个经典的技术面试题目:“从大量无序数中找到最大的K个数”。这个问题看似简单,但深入分析会发现其背后涉及了多种算法和技术细节。 #### 解法一:完全排序 - **基本思路**:首先对整个数组进行...

    算法中最小K元素的选择问题

    在计算机科学中,"算法中最小K元素的选择问题"是一个重要的数据结构和算法主题,它涉及到从一个无序或有序的数组中找到第K小(或大)的元素。这个问题在各种应用场景中都有广泛的应用,比如数据库查询优化、排序算法...

    数据结构与算法题解

    - 实例问题:给定一个无序数组,使用归并排序算法进行排序。 - **快速排序(QuickSort)** - 通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小。 - 实例问题:对一个整数...

    php数组冒泡排序算法实例

    示例代码中定义了一个名为`$array`的数组,包含了11个无特定顺序的整数,这是我们要进行排序的数据源。 2. **计算数组长度**: 使用`count()`函数获取数组的元素个数,并将其赋值给变量`$len`。这将用于后续的...

    C语言TOP-K问题(从一堆数据中找出最大的k个数或者最小的k个数)

    在C语言中,处理大数据集并找出其中最大的k个数或最小的k个数是一个常见的问题,这通常涉及到数据结构中的“堆”概念。堆是一种特殊的树形数据结构,满足以下性质:每个父节点的值要么大于等于其子节点(大顶堆),...

    05丨数组:为什么很多编程语言中数组都从0开始编号?1

    但在无序数组中,为了减少移动,可以将待插入元素放到数组末尾,或者将原位置的元素移动到末尾,然后将新元素插入原位置,这种方法在某些情况下可以提高效率。 数组在编程语言中的实现通常与基本数据类型有关。例如...

    选择第k小问题.zip

    这个问题要求在一组无序的元素中找到第k小(或第k大)的元素,而不必对整个序列进行完全排序。在本案例中,我们关注的是如何使用分治策略来解决这个问题,并通过Python 3.7实现。 分治法是一种重要的算法设计策略,...

    lintcode算法分析和解答

    - 字符串是计算机编程中最常用的数据类型之一,用于存储一系列字符。 - 常用操作包括字符串查找、反转、替换等。 - **链表(LinkedList)** - 链表是一种动态数据结构,由节点组成,每个节点包含数据和指向下一个...

    JavaScript实现列出数组中最长的连续数

    JavaScript实现列出数组中最长的连续数的方法主要涉及数组处理和遍历技巧。在给定一个无序的整数数组后,目标是找到并返回其中最长的连续数字序列。例如,在数组[100,4,200,1,3,2]中,最长的连续数字序列是[1,2,3,4]...

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

    - **查找峰值元素(Find Peak Element)**: 在一个无序数组中找到任意一个局部最大值。 - **在旋转排序数组中搜索/Search in Rotated Sorted Array**: 在一个被旋转过的排序数组中搜索给定数字。 - **在旋转排序数组中...

    杨辉三角数组.zip

    杨辉三角中的每个数字都是一个组合数,表示在无序集合中选取特定数量元素的方法数。例如,第n行第k个位置的数字表示从n个不同元素中选择k个的组合数,记为`C(n, k)`或`nCk`。 6. **性质与应用**: - 行和:每一行...

    寻找第k小元素(vc)

    在这个问题中,我们要在数组中找到第k个最小的元素,同时考虑到数组中可能存在重复的元素。这个问题在实际应用中广泛出现,比如数据库查询优化、数据分析以及在线竞赛编程等场景。 在Visual C++环境下实现寻找第k小...

    快速排序输出第k小的数

    根据给定的代码片段,我们可以深入探讨如何利用快速排序算法来输出一个无序数组中的第k小的数。 ### 快速排序原理 快速排序是一种分而治之的排序算法,由英国计算机科学家托尼·霍尔(Tony Hoare)于1960年提出。...

    algo_third_第k小元素c++_

    在编程领域,寻找一个数组中的第k小元素是一项常见的任务,尤其在算法设计和数据结构的学习中占有重要地位。这个任务通常涉及到排序和查找技术,而在这个特定的案例中,我们使用C++语言来实现,并且采取了一种将元素...

    数据结构(耿国华,高等教育出版社)第二章线性表课后习题第5题答案

    线性表在实际编程中应用广泛,它可以是数组或链表的形式,用于存储一组有序或无序的数据。 描述中提到的任务是“编写一个算法,从顺序表中删除自第i个元素开始的k个元素”。顺序表是一种数据结构,其中元素按照线性...

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

    通过这种方式,我们可以得到一个二维数组,其中每个元素表示以该位置为右下角的最大子矩阵和。最后,遍历这个二维数组,找出最大的元素,即为最大字段和。 以上知识可以通过提供的压缩包文件“分治法”中的代码示例...

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

    快速排序算法也可以用来在O(n)的时间复杂度内查找无序数组中的第K大元素。快速选择算法是快速排序算法的一个变种,利用快速排序的思想,在数组中找到第K大的元素。快速选择算法的基本思想是,进行一次划分操作后,...

Global site tag (gtag.js) - Google Analytics