JAVA中寻找最大的K个数解法_java

这个题拿到之后首先会想到排序,排好序之后在选取选取最大的K个数。排序选择快速排序是个比较好的选择。
好了,让我们来进行第一个解法:快速排序
代码如下

复制代码 代码如下:

public static void quickSort(int[] arr, int start, int end) {
  if (start < end) {
   int key = arr[start];
   int right = start;
   int left = end;
   while (right < left) {
    while (right < left && arr[left] > key) {
     left --;
    }
    if (right < left) {
     arr[right] = arr[left];
    }
    while (right < left && arr[right] <= key) {
     right ++;
    }
    if (right < left) {
     arr[left] = arr[right];
    }
   }
   arr[right] = key;
   quickSort(arr, start, right-1);
   quickSort(arr, left+1, end);
  }
 }
 

快速排序之后,数组会是有序的,上面的排序是从小到大的,所以我们输出应该是下面这样

复制代码 代码如下:

                int k = 4;
  for (int i=arr.length-1; i>=arr.length-k; i--) {
   System.out.println(arr[i]+"  ");
  }

。第一个解法已经好了,但是有没有更好的办法。
答案是有的!我们可以选择部分排序,接下来我们使用选择排序来做解决这个问题。
代码如下:

复制代码 代码如下:

public static int[] selectSortK(int[] arr, int k) {
  if(arr == null || arr.length == 0) {
   return null;
  }
  int[] newArr = new int[k];
  List<Integer> list = new ArrayList<Integer>();//记录每次最大数的下标
  for (int i=0; i<k; i++) {
   int maxValue = Integer.MIN_VALUE; //最大值
   int maxIndex = i;
   for (int j=0; j<arr.length; j++) {
    if (arr[j] > maxValue && !list.contains(j) ) {
     maxValue = arr[j];
     maxIndex = j;
    }
   }
   if (!list.contains(maxIndex)) {//如果不存在,就加入
    list.add(maxIndex);
    newArr[i] = maxValue;
   }
  }
  return newArr;
 }

时间: 2024-09-22 15:53:29

JAVA中寻找最大的K个数解法_java的相关文章

O(N)的时间寻找最大的K个数

寻找N个数中最大的K个数,本质上就是寻找最大的K个数中最小的那个,也就是第K大的数. 可以使用二分搜索的策略来寻找N个数中的第K大的数.对于一个给定的数p,可以在O(N)的时间复杂度内找出所有不小于p的数. 寻找第k大的元素: #include <iostream> using namespace std; //快速排序的划分函数 int partition(int a[],int l,int r) { int i,j,x,temp; i = l; j = r+1; x = a[l]; //将

编程之美之2.5 寻找最大的K个数

[题目] 有很多无序的数,从中找出最大的K个数.假定他们都不相等. [解法一] 如果数据不是很多,例如在几千个左右,我们可以排一下序,从中找出最大的K个数.排序可以选择快速排序或者堆排序 [cpp] view plaincopy #include<stdio.h>   #include<stdlib.h>   int cmp(const void *a,const void *b){       return *(int *)a - *(int *)b;   }   int mai

寻找最小的k个数

题目描述 输入n个整数,输出其中最小的k个. 分析与解法 解法一 要求一个序列中最小的k个数,按照惯有的思维方式,则是先对这个序列从小到大排序,然后输出前面的最小的k个数. 至于选取什么的排序方法,我想你可能会第一时间想到快速排序(我们知道,快速排序平均所费时间为  n*logn  ),然后再遍历序列中前k个元素输出即可.因此,总的时间复杂度:  O(n * log n)+O(k)=O(n * log n)  . 解法二 咱们再进一步想想,题目没有要求最小的k个数有序,也没要求最后n-k个数有序

为什么Java中的HashMap&amp;lt;K, V&amp;gt;的get函数是get(Object key),而不是get(K key)?

帮别人的代码改bug,发现有一大堆bug是由get或者remove传递进去的参数类型不匹配而造成的. 比如: Map<Short, String> m = new HashMap(); m.put(new Short((short) 2), "2222"); System.out.println(m.get(2)); 上面的代码输出是null. 一般人很难发现传递进去的int和Short类型不匹配,而且IDE,编译器也没有提示.当然通过一些分析工具可以检查出来. 真的感到很

寻找最小的k个数(四种方法)

1 使用从大到小的优先队列保存最小的K个数,每次取出K个数之后的其余数和堆顶元素比较,如果比堆顶元素小,则将堆顶元素删除,将该元素插入 void topK(int arr[],int n,int k) { if(k>n) return; priority_queue<int> q; for(int i=0;i<n;++i) { if(q.size()<k) q.push(arr[i]); else { if(arr[i]<q.top()) { q.pop(); q.pu

详解Java中的数组与字符串相关知识_java

Java数组的定义和使用 如果希望保存一组有相同类型的数据,可以使用数组. 数组的定义和内存分配 Java 中定义数组的语法有两种: type arrayName[]; type[] arrayName; type 为Java中的任意数据类型,包括基本类型和组合类型,arrayName为数组名,必须是一个合法的标识符,[ ] 指明该变量是一个数组类型变量.例如: int demoArray[]; int[] demoArray; 这两种形式没有区别,使用效果完全一样,读者可根据自己的编程习惯选择

在java中使用dom4j解析xml(示例代码)_java

虽然Java中已经有了Dom和Sax这两种标准解析方式 但其操作起来并不轻松,对于我这么一个初学者来说,其中部分代码是活生生的恶心 为此,伟大的第三方开发组开发出了Jdom和Dom4j等工具 鉴于目前的趋势,我们这里来讲讲Dom4j的基本用法,不涉及递归等复杂操作 Dom4j的用法很多,官网上的示例有那么点儿晦涩,这里就不写了 首先我们需要出创建一个xml文档,然后才能对其解析 xml文档: 复制代码 代码如下: <?xml version="1.0" encoding=&quo

Java中List的使用方法简单介绍_java

Java中的List就是一种集合对象,将所有的对象集中到一起存储.List里面可以放任意的java对象,也可以直接放值. 使用方法很简单,类似于数组.  使用List之前必须在程序头引入java.util.*  import java.util.*; public class list { public static void main(String args[]) { List a=new ArrayList(); a.add(1);//在LIST a中添加1 System.out.print

多用多学之Java中的Set,List,Map详解_java

很长时间以来一直代码中用的比较多的数据列表主要是List,而且都是ArrayList,感觉有这个玩意就够了.ArrayList是用于实现动态数组的包装工具类,这样写代码的时候就可以拉进拉出,迭代遍历,蛮方便的. 也不知道从什么时候开始慢慢的代码中就经常会出现HashMap和HashSet之类的工具类.应该说HashMap比较多一些,而且还是面试经典题,平时也会多看看.开始用的时候简单理解就是个键值对应表,使用键来找数据比较方便.随后深入了解后发现 这玩意还有点小奥秘,特别是新版本的JDK对Has